perm filename NSF.F[DOC,TOB] blob
sn#044645 filedate 1973-05-22 generic text, type T, neo UTF8
00100
00200
00300
00400
00500 Proposal to
00600
00700 THE NATIONAL SCIENCE FOUNDATION
00800
00900 for
01000
01100
01200
01300 ADVANCED AUTOMATION DEVELOPMENT
01400
01500 by
01600
01700 THE STANFORD ARTIFICIAL INTELLIGENCE LABORATORY
01800
01900
02000 Jerome Feldman, Associate Professor of Computer Science
02100 Associate Director, Artificial Intelligence Laboratory
02200 Principal Investigator
02300
02400 Thomas Binford, Research Associate in Computer Science
02500 Associate Investigator
02600
02700 Richard Paul, Research Associate in Computer Science
02800 Associate Investigator
02900
03000
03100
03200
03300 February 1973
03400
03500
03600
03700
03800
03900
04000
04100
04200 Computer Science Department
04300
04400 School of Humanities and Sciences
04500
04600
04700 STANFORD UNIVERSITY
04800
04900 Stanford, California
00100 ABSTRACT
00200
00300
00400 The Stanford Artificial Intelligence Laboratory proposes to undertake
00500 a program in advanced automation over a period of one year at a cost
00600 of $143,391. This proposal is to continue and extend programs
00700 sponsored under ARPA Contract SD-183.
00800
00900 This proposal is for initial study and preliminary research on a
01000 three year "proof of concept" project in computer controlled
01100 automatic assembly. The outline of the project has been worked out
01200 with industrial and governmental advice, but more analysis as well as
01300 more research is needed.
01400
01500 The project includes a pilot assembly station carrying out practical
01600 assembly tasks, a hardware-software system ready for production, and
01700 fundamental work on the underlying problems of vision, manipulation
01800 and problem-solving. We believe the laboratory is uniquely qualified
01900 to carry out this program which will be an important contribution to
02000 increasing industrial productivity.
02100
02200 Our basic approach involves a general purpose system integrating
02300 sensors and manipulators controlled by sophisticated programs in a
02400 digital computer. We have worked with such systems since 1965 and
02500 have developed many of the basic ideas required in general purpose
02600 assembly devices. The main thrust of this proposal is to establish
02700 the practicality of our methods and carry their development to a
02800 point from which industry can take over.
02900
03000 The research program is divided into four main sections: Pilot
03100 assembly station, vision development, manipulation development, and
03200 systems support. Each section contains a brief description of the
03300 laboratory's past work in the area, how it is to be applied, and what
03400 extensions are to be undertaken. Finally, we consider a number of
03500 important issues concerning our relations with industry and with
03600 other reseach and development efforts in advanced automation.
03700
03800
03900 TABLE OF CONTENTS
04000
04100 Part Page
04200
04300 I The Need for Advanced Automation ......................
04400 II Research Plan .........................................
04500 A. The Pilot Assembly Station ....................
04600 B. Research in Vision ............................
04700 C. Manipulator Development .......................
04800 D. Systems Requirements for Advanced Automation ..
04900 III Dissemination of Results and Relation with Industry ...
05000 IV Staff .................................................
05100 V Computing Facilities ..................................
05200 VI Budget ................................................
05300 VII References ............................................
05400 VIII Relevant Laboratory Publications ......................
05500 IX Films .................................................
05600 X Cognizant Personnel ...................................
00100 I. THE NEED FOR ADVANCED AUTOMATION
00200
00300
00400 The contributions that advanced automation can make to enhance
00500 productivity in manufacturing are now widely appreciated. Current
00600 interest in advanced computer-oriented automation stems from two
00700 sources. The first is the decreasing cost of computation combined
00800 with an improved understanding of how to apply computation to various
00900 aspects of manufacturing. The second cause is the realization that
01000 many current manufacturing operations, primarily assembly and
01100 inspection, will require complex automation methods which are now
01200 research techniques. The same considerations apply to the automation
01300 of tasks such as laboratory and medical procedures, but the emphasis
01400 has been (as ours will be) on manufacturing. A recent ARPA-sponsored
01500 study [Anderson 1972] in which we participated suggests the following
01600 major benefits from advanced automation:
01700 improved national productivity
01800 reduced prices
01900 increased product quality and uniformity
02000 customization of products
02100 increased job satisfaction.
02200 We would like to add just one comment. As we have seen with other
02300 technological developments such as numerical-controlled tools, there
02400 will be things made which were previously impractical to make. There
02500 is widespread agreement in the technical, industrial and government
02600 communities on the potential benefits of advanced automation. There
02700 is much less agreement on the level of sophistication needed in
02800 automation hardware and software. While there are large application
02900 areas in which specially constructed machines or simple general
03000 purpose devices will prove optimal, we believe that the most
03100 practical solution for intermediate quantities (500 to 100,000) will
03200 be to develop general purpose assembly and inspection devices
03300 controlled by sophisticated programs in digital computers.
03400
03500 Several studies have indicated some priorities among directions of
03600 automation. The ISI study [Anderson] indicates that less than 20% of
03700 discrete manufacturing is amenable to special purpose automation. A
03800 Chrysler Corporation study indicates that car assembly labor has
03900 first priority in automation; assembly plant direct labor is 40% of
04000 direct corporate labor. It was felt that automation was essential in
04100 the small parts division. The ISI study quotes a figure of 75% as the
04200 fraction of batch produced discrete manufactures. One conclusion is
04300 that "the emphasis in development should be on simple vision devices
04400 and on low-bandwidth tactile and force sensing feedback". That study
04500 indicates that the assembly process typically accounts for 50 percent
04600 of production cost. Although such estimates are crude, the study
04700 indicates a potential savings of $27 billion on manufactures which
04800 total $492 billion.
04900
05000 We assume that present manipulators have a small but stable market,
05100 and that most will have minicomputers soon (Sundstrand does now).
05200 Will the incremental cost of touch, force and visual sensors be
05300 offset by the opening of new capabilities, and will the cost be
05400 offset by reduced cost of system design for machines which allow
05500 loose alignment tolerances? We estimate that touch and force sensing
05600 will add about 5% to the price of current manipulators of the Unimate
05700 class. We estimate that by 1977, the incremental cost of visual
05800 sensors, a laser ranging device such as we use now,and additional
05900 memory requirements, will add about 15%-20% to current manipulator
06000 prices. If labor costs continue to rise, part of the increase will be
06100 offset, but cost comparisons will not change appreciably over that
06200 time scale unless significant new mechanical designs are made. A
06300 conclusion is that sensor-equipped robots will be available at slight
06400 additional cost. We explore the benefits of incremental improvements
06500 to manipulators.
06600
06700 We do not expect mechanical production costs to drop as dramatically
06800 as electronics costs fall with integration. The most promising cost
06900 reduction development would be high-production standard modules such
07000 as robots. As an example, consider the Stanford arm; produced in
07100 unit quantity, parts, manufacturing and assembly costs are
07200 approximately $10K. The arm is much simpler than an automobile; there
07300 is no reason why it should cost more. A smaller, more recent design
07400 sells for $3500 in quantities of two.
07500
07600 A robot with two arms, minicomputer control, force and touch sensors
07700 could be constructed for under $10K in quantities of 1000 now. To
07800 summarize: two arms (new small Scheinman design) $2000 with hand; arm
07900 drivers and arm interface electronics $1000; force and touch $800;
08000 small computer 8k memory $4500; total $8300. Assuming that the
08100 computer price falls to $1200 by 1978, the cost is $5000. Of course,
08200 these are small arms, suited for parts assembly, not automotive body
08300 assembly. The larger arms, assuming slight redesign for cost
08400 consciousness, would cost about $2500 in units of 1000, for a total
08500 system cost (not price) of $12300, falling to $9000 by 1978. This is
08600 the range of price of present transfer machines which have limited
08700 market because they have limited motion, no control, and are thus
08800 locked out of the economy of scale. There is a dynamic which leads to
08900 economy of scale; the greater the versatility, the wider is the
09000 market for applications. This will be true particularly in small
09100 production and job shop operations which have been difficult to
09200 automate. The larger the production, the more versatility for the
09300 same initial cost as special devices. Also, with high volume,
09400 standardization of maintenance, and availability of parts and service
09500 are improved. The quality of the device is also improved.
09600
09700 The economies of scale in production of assembly modules are matched
09800 by economies of intellectual scale in development of design for
09900 automation. The design process is modularized and easily
10000 communicable; there is a common discipline which can be widely
10100 absorbed; developments of many sources can be integrated. Programming
10200 and training done once for one machine can be transferred to all
10300 machines in a plant, and even transferred nationwide. Functional
10400 modularity has been emphasized in our studies. Modularity is clearly
10500 possible and there is a powerful economic incentive to assemble
10600 widely varying systems from one, two, or three arm modules, force and
10700 touch modules, vision and ranging modules, with planning and
10800 monitoring modules. This would also entail software modularity with
10900 computer-aided mechanical design and job specification for robots on
11000 a local or network time-sharing service.
11100
11200 The alternative is special design for each operation. We expect that
11300 at some point, design will be cheaper with standard robot modules
11400 than with special purpose designs, just as it is now more economical
11500 to use mini-computer controllers than special purpose controllers.
11600 Modularity has the potential to reduce design time and improve
11700 predictability of design time and costs, permitting better planning
11800 and response to competition. To some extent, the dehumanized
11900 industrial worker now fills the role of standard module, so that we
12000 do not expect discontinuous change. The continuity with decades of
12100 experience with design for human versatility in assembly can be
12200 relied upon; robots with some versatility, sensing, contingency
12300 actions, and dexterity will provide a transition to newer schemes
12400 which will evolve more slowly. Another advantage of general purpose
12500 techniques is the ease with which the size of the robot can be scaled
12600 up or down. There appears to be no difficulty in making very large or
12700 very small assembly stations which use essentially the same programs.
12800
12900 Versatile assembly devices have an efficiency advantage in medium
13000 scale and job shop production; their utilization efficiency can be
13100 higher because versatility allows a variety of operations to be
13200 scheduled at one station. The availability of computers for
13300 production scheduling will allow the flexibility to be used to
13400 advantage. Robots would also have longer life over which to amortize
13500 costs, since they could function with greatly changed production
13600 operations, and evolve with new hardware and software modules. They
13700 would have higher reliability, since they would have monitoring,
13800 contingency action, and error recovery. They would be self-aligning,
13900 self-calibrating, and self-testing.
14000
14100 With simple devices, inspection and assembly operations must be
14200 broken down into small operations with transfer operations between.
14300 This introduces extra transfer devices with orientation-preserving or
14400 re-orienting steps, and overlapping operations which can be combined
14500 in an advanced device. The extra cost of jigs and fixtures, and of
14600 stopping assembly lines adds to the cost of special purpose
14700 automation. Robots can cut down on real estate, since several
14800 operations can be done at one station.
14900
15000 Because of the adaptibility of work stations, a quicker response to
15100 market and competition is possible. Production runs can be smaller,
15200 with less capital tied up in inventory and unused machines. There
15300 can be better response to the needs of high technology industry which
15400 often requires small quantities. There has been difficulty in
15500 meeting the tight tolerances necessary for operation of
15600 non-intelligent devices. It is hard to estimate the value of systems
15700 which work within current industrial tolerance, rather than requiring
15800 radical improvements in engineering practice, but that continuity
15900 does seem important.
16000
16100 Serious issues arise in the development of robots with simple sensory
16200 systems. Some evaluation issues should be settled by demonstration,
16300 since much sharper analyses can be made this way. We propose to:
16400 demonstrate practical speed and dexterity with two arms and tool
16500 using. Demonstrate the generality of arm control and planning for
16600 various arms and devices. Demonstrate designs which standardize
16700 interface with devices and which lower interface costs. Demonstrate
16800 programming of assembly devices in an interactive APT-like system
16900 (develop the Stanford Assembly Robot Management System, ARMS); show
17000 the commonality of operations aong similar assembly tasks.
17100
17200 There is already a significant degree of industrial involvement in
17300 computer-aided assembly. GM Research Lab has demonstrated a wheel
17400 mounting operation using visual alignment. IBM has a small robot
17500 project. Hitachi has demonstrated a robot with touch and a system
17600 with visual identification of objects on a conveyor belt, with visual
17700 control of manipulation. Can industry be expected to adequately
17800 support this development? Development of primitive robots is an
17900 evolutionary process, not a single product development. Thus it is
18000 not possible to keep secret and maintain an enormous productivity
18100 advantage; the techniques are usable by everyone. The area is too
18200 big; the payoffs are huge and the investment level is large. Also,
18300 traditionally, industry has been dependent on suppliers. But with the
18400 exception of IBM, the suppliers are smaller and less able to risk the
18500 development. Management techniques require inordinate return on
18600 capital. An alternative support could come again from the military.
18700 The ARPA study and the history of numerical controlled machine tools
18800 are natural consequences of the vast military procurement in
18900 technologically advanced products. In the case of N/C, funds could be
19000 diverted from an outmoded technology to development of devices which
19100 were essential to production plans for the future. It is high
19200 technology products which are most competitive internationally in the
19300 civilian economy. The record of government investment in numerical
19400 control, solid state electronics, computers, and electro-optical
19500 devices has been very productive. However, in large scale development
19600 of civilian products and international markets, foreign governments
19700 have taken the lead. The development of general purpose assembly
19800 devices will benefit manufacturers in a broad spectrum of industry,
19900 particularly medium scale manufacturing. It is an appropriate area
20000 for governmental action to help meet a national need.
20100
20200 Given sensor-equipped robots at little extra cost, they will have
20300 visual ability to sense color, strong contrasts in brightness,
20400 recognize known objects from two dimensional outlines (top view of
20500 flat object) or three dimensionally using depth, to a certain extent
20600 they will be able to recognize three dimensional objects using
20700 monocular recognition. They will be able to visually align mating
20800 parts in assembly operations, increase reliability by self-
20900 calibration and flaw and disaster detection, and permit large
21000 tolerances in parts transfer, even permitting parts to be taken from
21100 a bin. Several of these abilities are not yet available in the
21200 laboratory, but with known conditions and objects, and some
21300 engineering (e.g. color coding) are achievable within the time span
21400 of the proposed project.
21500
21600 The major determinant of the economic impact of assembly robots will
21700 be the extent of their capabilities. Assessing and extending these
21800 capabilities is the principle goal of the proposed project.
21900
00100 II. RESEARCH PLAN
00200
00300 A. THE PILOT ASSEMBLY STATION
00400
00500 The basic goal of the proposed project is to implement a general
00600 purpose assembly station and to prove its applicability to real
00700 problems. The project will be considered a success if one or more
00800 enterprises chooses to manufacture and market the general purpose
00900 station. There are a number of hardware and software problems to be
01000 solved in meeting our goal.
01100
01200 In one configuration, the assembly station is assumed to be connected
01300 to a large time-shared computer facility. Not only does this appear
01400 to be a good design for our problem, but it is also necessary for an
01500 integrated programmed automation facility. The only emphasized
01600 statement in the ARPA study report [Anderson 1972] is: "The maximum
01700 impact of computers in manufacturing will come from complete,
01800 real-time computer cognizance and control of all processes and
01900 resources, allowing the precise scheduling and allocation of these
02000 resources."
02100
02200 Each assembly station will consist of a small digital computer, one
02300 or more manipulators and cameras. Manipulators and cameras will be
02400 combined as modules in systems to suit a given task, and will be
02500 digitally controlled by the station computer. The station computer
02600 may be connected to a central computer or may stand alone. The latter
02700 configuration is less efficient in the long run, but allows for
02800 incremental automation.
02900
03000 The program in the station computer will be flexible as to the number
03100 and position of manipulators and cameras. It will control input from
03200 the cameras, provide for some pre-processing of the picture and the
03300 application of simple tests to the visual data. In the case of
03400 manipulators it will provide for simultaneous servo control. It will
03500 also process other inputs, such as from touch sensors on the
03600 manipulators, from photocell interrupt devices, limit switches, etc.
03700 Both analog and binary outputs will be available for the control of
03800 other devices.
03900
04000 Each station computer will have access to a task program specifying
04100 the actions and tests it should perform to carry out its task. This
04200 task program will be compiled by the central computer. Compilation
04300 will consist of the analysis of predicted scenes in order to specify
04400 simple tests that the station computer can carry out, the calculation
04500 of collision free trajectories for the manipulators, the sequence of
04600 operations and simple contingency plans. etc. We are planning for
04700 tasks whose normal execution does not require detailed scene
04800 analysis. If scene analysis becomes necessary (e.g. a dropped part)
04900 we envision the station sending an image to the central computer for
05000 processing.
05100
05200 The central computer will perform overall control of the individual
05300 assembly stations and the relative rates of production. If at any
05400 station a planned test fails, for which a contingency plan does not
05500 exist, or any unexpected sensor signals are received, the central
05600 computer will also be interrupted and appropriate actions taken. If
05700 the assembly station is not connected to a central computer, these
05800 operations will require human intervention.
05900
06000
06100 Most of the hardware required for the assembly station has been
06200 developed for the laboratory. Manipulators and cameras will be
06300 discussed in detail below. The major additional problem is to refine
06400 the existing designs to meet the demands of an industrial
06500 environment.
06600
06700 We are now acquiring small computer such as the PDP-11 and will
06800 interface the existing arms to it together with one or more cameras.
06900 A software package for the small computer will then be developed in
07000 order to control the manipulators, read the TV cameras and to perform
07100 low level visual analysis. Programs to plan tasks, calibrate the
07200 system and to perform higher level visual analysis, error recovery
07300 and strategy planning will be written in a high level language for
07400 the time-sharing processor.
07500
07600 The most difficult part of the assembly station, and the heart of the
07700 project is a demonstration of the feasibility of the station. We plan
07800 to do this by developing programs which actually assemble and inspect
07900 a variety of fairly complex manufactured items.
08000
08100 A typical example is our current effort, assembly of an automobile
08200 water pump. The major parts are to be located, the screws are
08300 supplied by a feeder, as is standard. Locating the body and cover of
08400 the pump require a gross localization, then a fine localization of
08500 screw holes. Touch provides a final accuracy and independent
08600 coordination of the hand. The placing of alignment pins within screw
08700 holes could be monitored visually; although in this case,the previous
08800 actions provide adequate accuracy. Placing of the cover over
08900 alignment pins can be carried out without vision. Improved force
09000 sensing now under development will be useful for that operation.
09100
09200 As we move to more difficult tasks, the sophistication required goes
09300 up quite rapidly. The current manipulation routines seem to be
09400 expandable to cover anticipated problems, especially since we intend
09500 to employ special purpose manipulators (tools) for some tasks. The
09600 main part of our effort will be vision for assembly; an assembly task
09700 will be performed using vision, touch, and two hands. The vision
09800 effort will be integrated with other abilities, and while no great
09900 generality will be stressed, new modules will be incorporated into
10000 the system, and a set of techniques will evolve. These will depend
10100 heavily on techniques similar to those of our recent studies in
10200 visual feedback and hand/eye coordination [Gill 1972]. The internal
10300 model of the world will be used to predict visual appearance of
10400 selected areas of the scene, and a set of verification procedures
10500 will confirm or contradict the predictions. Many of the operations
10600 will be connected with supplying feedback to manipulation, for
10700 alignment and insertion. These visual procedures will have models for
10800 the parts and approximate locations.
10900
11000 This and other visual tasks connected with assembly will initially be
11100 performed as special case problems. In addition, to make these
11200 techniques available, we will pursue development of strategy
11300 programs. This step is essential if intelligent assembly devices are
11400 to be conveniently programmed for complex tasks. Within the division
11500 of labor between large and small machines, this facility must reside
11600 in the central time-sharing facility which has large memory, file
11700 storage, and problem-solving languages. The system must have a model
11800 of the parts for assembly,and a sequence of instructions for
11900 assembly. It will be necessary to have a representation of shape and
12000 models for usual assembly operations such as insertion and alignment,
12100 and the ability to solve simple problems in connection with these
12200 operations, all this to enable convenient communication with the
12300 user. When these facilities exist, the addition of new features and
12400 operations can be incorporated smoothly, so that users can call on a
12500 growing library of planning modules. The result of a planning effort
12600 is a cycle of machine planning and man-machine interaction which
12700 results in a plan network for the mini computer which controls
12800 individual machines.
12900
00100 B. RESEARCH IN VISION
00200
00300 Research in computer vision has progressed so that the larger part of
00400 our effort is directed toward vision in real scenes. We outline past
00500 research, including work on visual feedback, development of useful
00600 modules, analysis of some outdoor scenes, interpretation of scenes
00700 with curved objects, and a study of sensor systems.
00800
00900 Our past work on visual feedback [Gill 1972] in stacking blocks and
01000 inserting objects in holes is directly relevant to vision for
01100 assembly. The issues involved are: coordinating hand and eye,
01200 utilizing incremental accuracy of vision and manipulation, accurate
01300 prediction to limit search, and limiting accumulation of errors.
01400 Visual guidance in picking up objects and stacking or inserting
01500 objects overcomes errors in the visual and arm coordinate systems,
01600 and errors in correspondence between the two coordinate systems. This
01700 was done under realistic conditions, with the hand still holding the
01800 object and in view; the system predicts the appearance of edges and
01900 corners within a small window around the edges to be aligned, and
02000 uses a corner/edge finder to determine alignment error. The arm makes
02100 accurate incremental error correction. If predictions can be made
02200 accurately, the search window can be small, which increases the speed
02300 of response and decreases possibility of confusion with other areas
02400 of the scene. A major limitation to accuracy of prediction (and to
02500 long-term reliability in the industrial environment) is drift of
02600 calibration. That work incorporates calibration updating by
02700 self-calibration to coordinate hand and eye coordinate systems and
02800 provide for reliability, as well as to limit search by accurately
02900 predicting expected features. Visual feedback with stereo vision is
03000 much more powerful than without; we have demonstrated stereo visual
03100 feedback in a program [Binford unpublished].
03200
03300 We have a set of visual modules to be used in a goal-directed way.
03400 These modules answer questions which arise in practical visual
03500 feedback tasks, and in analysis of outdoor scenes. Are there color
03600 edges in a selected window? Are there edges in brightness? What is
03700 the color of the region in the window? Several preliminary color
03800 region analysis programs have been developed [Binford, unpublished,
03900 Bajcsy 1972]. An edge operator [Hueckel 1969] and a region-based
04000 corner/edge finder [Gill 1972] both operate on small windows of the
04100 scene, as directed by a higher level. An edge verifier is used to
04200 confirm or reject edges predicted from context [Tenenbaum 1970].
04300 Color identification has long been demonstrated. Recently, a program
04400 has been implemented [Thomas unpublished] based on Land's Retinex
04500 model of color constancy in vision, which defines a color triangle
04600 from ordering of brightnesses. The center of the triangle is
04700 designated as white. The program shows a color constancy similar to
04800 humans; table top scenes are assigned colors reasonably well under a
04900 variety of lighting with different spectra: sunlight, flourescent,
05000 and incandescent.
05100
05200 Understanding outdoor scenes is a more complex task than many
05300 industrial visual operations, but it has utility for planetary
05400 exploration; it is also a useful exercise for developing color,
05500 texture, and stereo operations. Bajcsy analyzed outdoor scenes with a
05600 combination of color and texture region analysis [Bajcsy 1972]; depth
05700 cues were taken from the gradient of texture. An attempt was made to
05800 obtain consistent interpretations by making three dimensional
05900 interpretations, and confirming boundaries by independent properties.
06000 Natural objects and natural scenes have been used for our work with
06100 motion parallax [Nevatia in draft] and stereo vision
06200 [Quam,Hannah].These are complementary techniques of depth perception
06300 which are applicable for planetary exploration and industrial tasks.
06400 Motion parallax can be used for planning of navigation and
06500 characterizing large scale terrain features, since it provides large
06600 baselines.
06700
06800 Another aspect of vision with direct application to industrial
06900 enviroments is explored in our work with curved objects. Current
07000 programs use depth information to make useful descriptions of objects
07100 like a doll, a toy horse, a snake, or a glove [Agin]. Programs can
07200 segment these objects into parts like legs, arms or fingers, and link
07300 these parts together to form descriptions of entire objects
07400 [Nevatia]. These operations are precursors to a recognition process.
07500 The work depends on a new representation of shape [Binford 1971] in
07600 terms of volume components and a part/whole segmentation. Primitive
07700 parts are described by an axis which is a space curve, and normal
07800 cross sections along the axis. The representation is based on a
07900 formalism, "generalized translational invariance". There are
08000 significant theoretical reasons why this representation leads to a
08100 natural choice of parts by simple procedures, in distinction to other
08200 suggested representations. We developed a laser ranging device
08300 [Binford 1970,Agin] which was operational two years ago. It is
08400 particularly interesting that the device adds a cost of only about
08500 $400 to the cost of a visual system.
08600
08700 A study of visual and depth ranging sensor has been carried out which
08800 provides a background for choosing sensors and interface, and making
08900 cost estimates [Binford 1972, Earnest 1967]. We have maintained a
09000 calibrated hand and vision system for several years [Sobel 1970], and
09100 have developed self-calibration techniques with one and two eyes
09200 [Yakimovsky unpublished, Hannah 1972, Gill 1972].
09300
09400 A system for understanding scenes of blocks from single views has
09500 been implemented [Falk 1970]; it segments objects, matches against
09600 internal models, predicts appearance from its assumptions, and
09700 searches for verification and contradiction based on the predicted
09800 image. Support and spatial relations are also obtained. There has
09900 been past work on programs to obtain line drawings as input to
10000 recognition systems. An earlier system was based on limited context
10100 of expecting continuation of edges at vertices and predicting missing
10200 edges in certain expected configurations [Grape 1970]. A more recent
10300 approach has been to use models within the process of generating line
10400 drawings, so that the most efficient next guess can be made and
10500 context used intrinsically in the formation of line drawings.
10600
10700 VISION FOR ASSEMBLY
10800
10900 This is a key part of the proposed project. We propose to evaluate
11000 and implement visual facilities required by a robot with simple
11100 vision, in conjunction with force and touch. These facilities must be
11200 modularized by working out several examples, and made fast enough and
11300 small enough to be practical for a minicomputer-based robot. We have
11400 considerable experience with such standardization, and with visual
11500 feedback techniques in the domain of blocks. We are now at work on
11600 extending visual feedback techniques to typical assembly tasks. We
11700 are also evaluating methods of automating visual feedback. We have
11800 well-developed systems for modeling objects from the console and to
11900 predict their appearance using techniques from computer graphics
12000 [Baumgart 1972a,b]. We can predict curved edges from our models. We
12100 will use simple region analysis programs and edge operators to locate
12200 curved edges predicted within a small window. Automated visual
12300 feedback would combine with evolving strategy programs in an
12400 interactive system, Assembly Robot Management System, ARMS. We will
12500 maintain a calibrated system and improve calibration updating so that
12600 reliability is maintained at a high level.
12700
12800 We have developed a special case program for locating the pump body
12900 in the pump assembly and moving it to the standard location. We are
13000 at work on several other such tasks involved in the pump assembly
13100 which contain components of general utility for visual feedback.
13200 These tasks are typical of the simple visual operations which we will
13300 implement or adapt.
13400
13500 VISION RESEARCH
13600
13700 While continuing research activities are not to be supported by the
13800 proposed project, in all likelihood, the research will suggest useful
13900 programs for the assembly system, particularly work in recognition of
14000 complex objects using depth data. The computer now has symbolic
14100 internal models of objects. We are now in a position to recognize
14200 objects such as a glove, a hammer, etc. We will immediately deal
14300 with matching descriptions for recognition. The important extensions
14400 we wish to deal with are occlusion and access to a large visual
14500 memory. These will involve matching of partial descriptions and
14600 encoding of partial descriptions as indices to a small class of
14700 similar shapes, which can then be compared in more detail. We are
14800 working toward making the hardware stable enough that it can maintain
14900 calibration, and software streamlined so that the depth measurement
15000 system can be integrated with other hand/eye facilities. We intend
15100 to apply large parts of our programs for description and recognition
15200 of curved objects using only monocular intensity information. This is
15300 a much harder problem, but within our representation, shares much of
15400 the same code, and relies on the same conceptual basis of local
15500 three-dimensional models.
15600
15700
15800 There is a growing effort on navigation of vehicles in outdoor
15900 scenes. While this is not directly relevant to the industrial
16000 environment, it does reflect the growing involvement in complex
16100 visual tasks, and will lead to further development of an integrated
16200 visual system. One approach which has already given initial results
16300 [Yakimovsky] is to combine region growing with interpretation using a
16400 world model. Thus, regions are combined not simply on the basis of
16500 uniformity but because combining them improves the interpretation. At
16600 the same time, we will be combining more facilities into these visual
16700 systems, and more usable knowledge in the world model.
16800
16900 C. MANIPULATOR DEVELOPMENT
17000
17100 Manipulator research began at Stanford Artificial Intelligence
17200 Laboratory in 1965 with the acquisition and programming of a
17300 prototype Rancho Orthotic Arm. A later version of this arm was used
17400 in vision directed block stacking programs.
17500
17600 Our present arm, the result of a continuing design project, replaced
17700 the Rancho Arm in 1970. This arm like its predecessor was controlled
17800 by a digital servo program running under the time sharing computer.
17900 The new arm was used in the "Instant Insanity" demonstration in 1971.
18000 A second arm of the same type, with only minor modifications, is
18100 currently being interfaced to the computer. Both arms will share a
18200 common work space and will be able to be used individually, or
18300 together for two handed tasks.
18400
18500 Each joint of the arm is calibrated in terms of torque versus drive
18600 level and it is possible to predict the joint drive levels to produce
18700 a given force at the hand. Further, for the hand to exhibit degrees
18800 of freedom of motion, various joints are selected to be "free", that
18900 is to have no position feedback applied to them. By exerting a force
19000 at the hand and providing that certain degrees of freedom exist it is
19100 possible to perform a much wider class of tasks than simple
19200 positional control, for instance screwing in screws, mating parts,
19300 inserting tools and turning cranks.
19400
19500 Touch sensors on the fingers allow the hand to sense objects without
19600 disturbing them. When activated the arm will stop when any of the
19700 sensors touch. Branching arm instructions can test the state of the
19800 sensors and modify the execution of an arm program. When screwing a
19900 nut onto a bolt, for instance, the hand is first centered over the
20000 bolt by touching it.
20100
20200 Control of the arms is by a series of high level instructions; these
20300 instructions may be executed directly, or may be assembled together
20400 into an arm program. Arm programs may then be executed, as desired,
20500 by the control program. The control instructions may be accessed
20600 directly by other programs, using the message procedure mechanism, or
20700 in the form of symbolic source file.
20800
20900 Positional accuracy at the hand is typically 0.1 inches with
21000 repeatability of 0.02 inches. Force control at the hand is within 10
21100 ounces. The data rate to run the arm from an assembled arm program is
21200 of the order of 100 bits/second.
21300
21400 Manipulator research moves ahead simultaneously on three fronts:
21500 control, primitives and devices. Tasks are translated into an
21600 existing hand language and where the task cannot be accomplished in
21700 terms of existing primitives, new primitives are formulated in a
21800 consistent manner. When a new primative is formulated, real time
21900 routines are developed to perform the action. This also leads, in
22000 many cases, to the development of new hardware. Also as new
22100 developments occur in hardware design, existing real time routines
22200 are either re-written or modified.
22300
22400 Research is now concentrating on the following areas:
22500
22600 Strain gauge instrumentation of the wrist, in order to allow for more
22700 sensitive interaction of the hand with a task. High resolution,
22800 high sensitivity touch sensors, to increase tactile recognition and
22900 control abilities. These developments will lead in turn to new
23000 control concepts.
23100
23200 Development of tools for the hand. These tools can be instrumented
23300 such that the computer can feel and or see at the end of the tool.
23400 This should be a very important area of research as it goes beyond
23500 present human capabilities.
23600
23700 Two handed arm control, the planning and execution of tasks requiring
23800 the coordinated motion of both arms. This will require an extension
23900 of the existing servo program and the analysis of synchronization
24000 problems. The development of collision avoiders, so that arms will
24100 not collide with other objects and with each other.
24200
24300 Modification of the existing arm design to provide for better
24400 incremental motions, more degrees of freedom and a more rugged design
24500 suitable for industrial use. Development of arm and eye computer
24600 interfaces. These contain synchronized analog/digital converters
24700 for input and current controlled drivers for output.
24800
24900 The development of new hands is expected as more complex tasks are
25000 attempted. At present, with only one hand, we have been performing
25100 the positioning type of hand actions. When the second arm is
25200 operational we will be able to perform holding and pulling actions as
25300 well.
25400
25500 D. SYSTEM REQUIREMENTS FOR ADVANCED AUTOMATION
25600
25700 A key element in the development of any large programming effort is
25800 the software support. There has been continual effort along these
25900 lines at the Stanford Artificial Intelligence Laboratory and many
26000 useful ideas have been developed. We propose to extend the research
26100 along two separate lines: support for research and system software
26200 for operating automated systems. We will briefly describe our past
26300 efforts in this area and what we propose to undertake.
26400
26500 The Stanford Artificial Intelligence Laboratory has pioneered in
26600 several areas of system programming, including timesharing sys36700
26700 interactive graphics, and programming languages.
26800
26900 A great deal of additional effort has gone into direct support of
27000 hand-eye research. Very early, we established a set of standard
27100 formats and library routines [Pingle 72a]. A programming language,
27200 SAIL[Swinehart], was implemented in 1968. The language incorporates
27300 special features for large real-world-oriented problem solving
27400 systems and is currently in use at a number of Artificial
27500 Intelligence and other laboratories.
27600
27700 As we began to assemble larger and more sophisticated collections of
27800 programs, we felt a need for flexible mechanisms for cooperating
27900 sequential processes. The resulting monitor and language features
28000 [Feldman & Sproull 1971] have worked well for us and have been
28100 influential on other projects. Recently, we have added an
28200 additional set of features to SAIL to facilitate non-deterministic
28300 and event-directed programming[Feldman 1972]. The early reactions
28400 to this work, both within the laboratory and without has been very
28500 encouraging.
28600
28700 We expect relatively little work to be needed on further systems
28800 support for basic research. There will undoubtedly be efforts to
28900 take advantage of new hardware and of new programming ideas that may
29000 develop in the course of this program. Almost all of this work
29100 should be covered by other funding.
29200
29300 The development of software for the assembly station will require
29400 more of our effort. The central-local computer configuration
29500 requires code to be resident in the local computer and in the shared
29600 machine. The low level programs in the local machine will not be
29700 modified often, thus we can assume that a compiler resident in the
29800 central machine will suffice. The planning programs and general
29900 vision programs will be resident in the shared system. There are two
30000 possible configurations for the shared computer system: A PDP-10
30100 equivalent machine or a software package in ASA Standard Fortran IV
30200 which will run on any sufficiently large machine. One of the tasks
30300 under this proposal would be to evaluate these two alternatives.
30400
30500 A major share of the programming research effort will be concentrated
30600 on developing a programming system for automated assembly. This will
30700 combine ideas from our past work on languages, representation,
30800 computer graphics and arm control. We view this task as a branch of
30900 the larger effort on automatic programming being undertaken in this
31000 laboratory and elsewhere.
31100
00100 III. UTILIZATION PLAN-DISSEMINATION OF RESULTS AND RELATION WITH
00200 INDUSTRY
00300
00400
00500 There are several other efforts, at varying levels of sophistication,
00600 in the area of computer controlled advanced automation. The Stanford
00700 Artificial Intelligence Laboratory is the oldest and largest of these
00800 and has provided the cutting edge of much of he development. We
00900 intend to continue this role and to lead in the development of a
01000 practical general purpose assembly system and the associated
01100 software.
01200
01300 All of the discoveries made under this grant will, of course, be made
01400 public. We view our role in information transfer in a much broader
01500 way. Having no desire to sell products and services and no clients
01600 with interests to protect, a university laboratory should be
01700 primarily a place for acquiring and spreading knowledge.
01800
01900 The Stanford Artificial Intelligence Laboratory has always considered
02000 information transfer to be one of its primary goals. In addition, to
02100 our published papers and reports, we have made a number of film
02200 reports which have been extensively circulated. There have been
02300 thousands of visitors, ranging from elementary school classes to
02400 major scientific, governmental and industrial missions from many
02500 countries. We have also encouraged extended visits by workers from
02600 other laboratories and from industry. Members of the laboratory staff
02700 have played a major role in the organization of journals, conferences
02800 and seminars in artificial intelligence. Many of our algorithms,
02900 systems, and hardware designs have been adopted by other groups.
03000
03100 The success of the program proposed here depends heavily on
03200 interaction with industry. We will need additional information on
03300 the opportunities for automation and will try to involve manfacturers
03400 in the development of the pilot assembly station. We have good
03500 working relationships with a number of firms and we expect that a
03600 concrete project will help forge the bonds necessary for the transfer
03700 of advanced automation technology from the laboratory.
03800
03900 One promising approach to technology transfer is a staff associates
04000 program. This involves residence of about a year's duration at the
04100 laboratory by industrial scientists. Such a program was used
04200 successfully at the MIT, Electronic's Research Laboratory in the area
04300 of programming systems for numerically controlled tools and design
04400 automation. We have initiated a similar program in the laboratory
04500 (cf Appendix A) and are pursuing additional forms of cooperation.
00100 Appendix A
00200
00300 The Stanford A.I. Lab has been engaged in research on
00400 advanced automation technology. Our work has progressed to the stage
00500 where we are seriously engaged in developing and disseminating
00600 practical applications. To do this effectively, we will need the
00700 help of industrial organizations with computer sophistication and an
00800 understanding of practical problems. One form of cooperation which
00900 we are engaged in is a staff associates program. A staff associate
01000 is a member of another organization in residence at the A.I. Lab. We
01100 have had a number of staff associates over the years, mostly from
01200 foreign countries. The enclosed letter from Japan is typical of the
01300 inquiries we receive. The purpose of the new program is to invite a
01400 few domestic inductrial organizations to submit candidates for the
01500 staff associates positions.
01600
01700 We expect to be able to have three to five staff associates
01800 in the laboratory at a time. The associate would remain for about a
01900 year and would be paid by his sponsoring organization. He would be a
02000 regular member of the laboratory staff, working on automation
02100 problems.
02200
02300 There are, of course, academic programs at Stanford which
02400 could also involve work at the Artificial Intelligence Lab. The
02500 staff associate program differs in that the selection criteria are
02600 different, the timing more flexible, and the expected time devoted to
02700 course work much less. We believe that it is the most effective
02800 mechanism for us to learn from and help industrial practitioners of
02900 computer-aided advanced automation.
03000
03100
03200 Jerome A. Feldman
00100 IV. STAFF
00200 Brief Biographical Sketches
00300
00400 Jerome A. Feldman, Principal Investigator: Early training in physics
00500 and mathematics; Ph.D. in computer science from Carnegie-Mellon,
00600 1964. Two years at M.I.T. Lincoln Laboratory. At Stanford since 1966,
00700 leader of Robotics group since 1968. currently Associate Professor of
00800 Computer Science and Associate Director of the Artificial
00900 Intelligence Lab. Research interests include Robotics, associative
01000 processing, inductive inference, and Translator-writing systems.
01100
01200 Thomas O. Binford, Associate Investigator: Received PhD in physics
01300 from the University of Wisconsin, 1965, working with strange particle
01400 reactions, Regge pole and group theory phenomenology. Fulbright
01500 1965-66 Tata Institute of Fundamental Research, Bombay, India: phase
01600 shift analysis of strange particle systems; theory of unstable
01700 particles. At MIT Artificial Intelligence Project 1967-70, working
01800 on representation of shape, region-based analysis system and other
01900 areas of computer vision, systems programming for LISP. Lecturer in
02000 computer science at Stanford University. Research interests are
02100 computer vision, robotics, representation, and perception.
02200
02300 Richard P. C. Paul, Associate Investigator: Undergraduate work in
02400 Engineering Physics at McGill, Masters in Electrical Engineering and
02500 PhD in Computer Science at Stanford University. From 1963 at the
02600 Stanford Linear Accelerator Center as Electronic Engineer. At the
02700 Stanford A. I. Laboratory since 1966 and responsible for manipulator
02800 systems development since 1968. Research interests include Robotics
02900 and digital servo systems.
03000
03100 John McCarthy: BS in Math., Cal Tech, PhD in Math, Princeton, 1951.
03200 With Minsky, organized and directed the Artificial Intelligence
03300 Project at MIT. Joined Stanford as Professor of Computer Science in
03400 1962. Organized and directs the Stanford Artificial Intelligence
03500 Lab. Research interests include nearly all aspects of artificial
03600 intelligence, timesharing systems, mathematical theory of
03700 computation, and representation theory.
03800
03900 Victor Scheinman: Bachelor's in Electrical Engineering, M.I.T.,
04000 Engineer's in Mechanical Engineering from Stanford, 1969. Employed
04100 as a design engineer at Stanford, M.I.T., and Raychem since 1969.
04200 Responsible for the design and construction of computer controlled
04300 arms, as well as other Robotics equipment such as color-wheels, focus
04400 controls, pan-tilt heads, etc.
04500
04600 Lester Earnest: BS in Electrical Engineering, Cal Tech; MS in
04700 Electrical Engineering, MIT, 1960. Two years at MIT Lincoln
04800 Laboratory. Seven years at Mitre Corporation, ending as Head of
04900 Information Systems Department. At Stanford since 1965 as Executive
05000 Officer and Associate Director of the Artificial Intelligence
05100 Laboratory, Research Computer Scientist, and Lecturer in Computer
05200 Science. Responsible for administration and industrial liason.
05300
05400
05500
05600 Curriculum Vitae
05700
05800 JEROME A. FELDMAN
05900
06000 1972
06100
06200
06300 Biographical Information:
06400
06500 Born: December 5, 1938 in Pittsburgh, Pennsylvania, U.S.A.
06600 Nationality: United States
06700 Marital Status: Married, two children
06800
06900
07000 EDUCATION:
07100
07200 B.A. (Physics, with Distinction) Rochester 1960
07300 M.A. (Mathematics) Pittsburgh 1961
07400 Ph.D. (Mathematics, Computer Science) Carnegie-Mellon 1964
07500
07600
07700 HONORS AND SOCIETIES:
07800
07900 Association for Computing Machinery
08000 American Association for the Advancement of Science
08100 National Lecturer, Association for Computing Machinery 1966
08200 Best Session Award, IEEE, August 1970
08300 Fulbright Lecturer, Hebrew University, Jerusalem 1970-71
08400
08500
08600 PROFESSIONAL EXPERIENCE:
08700
08800 Engineer, Westinghouse Electric Corporation 1960-61
08900 Asst. Research Scientist, Carnegie-Mellon U. 1963-64
09000 Staff Member, MIT Lincoln Laboratory 1964-66
09100 Summer Lecturer, U. Pennsylvania 1966
09200 Summer Lecturer, U. Michigan 1967
09300 Asst. Prof., Computer Science, Stanford U. 1966-69
09400 Assoc. Prof., Computer Science, Stanford U. 1969-Present
09500 Visiting Prof. of Computer Science, Hebrew U. 1970-71
09600 Assoc. Dir., Artificial Intelligence Lab., Stanford U. 1972-Present
09700
09800
09900
10000 EDITORIAL, ORGANIZATIONAL, AND CONSULTATION:
10100
10200 Reviewer for Computing Reviews, Journal and
10300 Communications of the ACM, Information and
10400 Control, IEEE Computer Group, various Conferences
10500 and government agencies.
10600
10700 Consultant for IBM, Systems Development Corp.,
10800 Martin-Marietta Corp., Lockheed Missiles and Space
10900 Corp., General Motors, National Institute of Health
11000
11100 Editorial Board, Fundamental Studies in Computer
11200 Science, North-Holland Publishing Company
11300
11400 Lecturer, ACM Professional Development Seminar in
11500 Time-Sharing, 1967
11600
11700 Organizing Committee, Israel Alta Conference,
11800 Ashkelon, February 1971
11900 NATO Conference on Software, Rome,Italy,1969
12000 ACM Conf. on Very High Level Languages, 1974
00100 PUBLICATIONS
00200
00300 Jerome A. Feldman
00400
00500
00600 "Some Regularity Theorems on Kernel Methods of Summation for
00700 Functions of a Complex Variable," Masters' Thesis, U. of Pittsburgh,
00800 1961.
00900
01000 "A Formal Semantics for Computer Oriented Languages", Ph.D.
01100 Dissertation, May 1964, Carnegie-Mellon University.
01200
01300 "Aspects of Associative Processing", TN-1965-13, Lincoln Laboratory,
01400 Massachusetts Institute of Technology, Lexington, Massachusetts.
01500
01600 "A Formal Semantics for Programming Languages", Proceedings of the
01700 International Federation of Information Processing Societies, May
01800 1965.
01900
02000
02100 "A Formal Semantics for Computer Languages and its Applications in a
02200 Compiler-Compiler", Communications of the Association for Computing
02300 Machinery, Vol. 9, No. 1, January 1966, and reprinted in "COMPUTER
02400 COMPILER TECHNIQUES", Auerbach Publishers, 1971.
02500
02600 "An Associative Processing System for Conventional Digital
02700 Computers", (with P.D. Rovner), TN-1967-19, Lincoln Laboratory, MIT,
02800 Lexington, Mass.
02900
03000
03100 "The Compiler-Compiler in a Time-Sharing Environment", (with J.
03200 Curry), Summer Lectures on Advanced Computer Organization, University
03300 of Michigan, June 1967. Also Bit Dropper, September 1967.
03400
03500 "Translator Writing Systems", (with D. Gries), CS 69, Computer
03600 Science Department, Stanford University, June 1967.
03700
03800 "First Thoughts on Grammatical Inference", A.I. Memo 55, Stanford
03900 University, August 1967.
04000
04100 "Translator Writing Systems", (with D. Gries), Communications of the
04200 Association for Computing Machinery, Vol. 11, No. 3, March 1968, and
04300 reprinted in "Computer Compiler Techniques", Auerbach Publishers,
04400 1971.
04500
04600 "The Leap Language and Data Structure", (with P.D. Rovner), Lincoln
04700 Laboratory Memorandum, January 1968. Also in reduced form in
04800 Proceedings of the International Federation of Information Processing
04900 Societies, August 1968.
05000
05100 "Grammatical Inference and Grammatical Complexity", (with others), CS
05200 125, Stanford University, Computer Science Department, Stanford,
05300 California, May 1969.
05400
05500 "An Algol-based Associative Language", (with P.D. Rovner), A.I. Memo
05600 66, Stanford University, 1968. Also Communications of the ACM, Vol.
05700 12, No. 8 August 1969, pp. 439-449. Reprinted in, INTRODUCTION TO
05800 INFORMATION SCIENCE (T. Saracevic, Ed.) Bowker, 1971.
05900
06000 "The Stanford Hand-Eye Project", (with others), Proc. First
06100 International Congress on Artificial Intelligence, Washington, D.C.,
06200 May 1969.
06300
06400 "The Computer Description of Simply Described Scenes", (with R.P.
06500 Paul and G. Falk), A.I. Memo 101, Stanford University. Also in,
06600 PERTINENT CONCEPTS IN COMPUTER GRAPHICS, (J. Nievergelt and M.
06700 Faiman, Eds.), U.of Illinois Press, 1969.
06800
06900 "Machine Intelligence", Review of Numbers I.III of the Machine
07000 Intelligence Series, Information and Control, 14, 490-492, 1969.
07100
07200
07300 "Towards Automatic Programming", Preprints of the NATO Software
07400 Engineering Conference, Rome, Italy, 1969.
07500
07600 "Getting a Computer to See Simple Scenes", IEEE Student Journal,
07700 September 1970.
07800
07900 "A Survey of Grammatical Inference", (with A. Biermann), Proceedings
08000 of International Congress on Pattern Recogniton, Honolulu, January
08100 1971. also in S. Watanbe (Ed.) FRONTIERS OF PATTERN RECOGNITION,
08200 Academic Press, 1972.
08300
08400 "Hebrew University Production Language", (with S. Tsur and D. Lehman)
08500 Hebrew University, Computer Science Department, February 1971.
08600
08700 "A Way of Looking at Things", Hebrew University, Computer Science
08800 Department, February 1971.
08900
09000 "A Laboratory for Hand-Eye Research", (with others), Proceedings
09100 IFIPS International Conference, Lubljana, Yugoslavia, August 1971.
09200
09300 "System Support for the Stanford Hand-Eye Project", (with R. Sproull)
09400 Proceedings Second International Congress on Artificial Intelligence,
09500 London, September 1971, p. 183-189.
09600
09700 "The Use of Vision and Manipulation to Solve the Instant Insanity
09800 Puzzle", (with others), Proceedings Second International Conference
09900 on Artificial Intelligence, London, September 1971, p. 359-364.
10000
10100 "Some Decidability Results on Grammatical Inference and Complexity",
10200 Information and Control, Vol. 20, No. 3, April 1972, p. 244-262.
10300
10400 "On The Synthesis of Finite-State Machines from Samples of their
10500 Behavior", (with A. Biermann), IEEE Transactions on Computers, June
10600 1972, Vol. C-21, No. 6, p. 592-596.
10700
10800 "Automatic Programming", CS 255, Stanford University, Computer
10900 Science Department, Stanford, California, February 1972.
11000
11100 "Total Complexity and the Inference of Best Programs", (with P.
11200 Shields), CS 253, Stanford University, April 1972. Submitted to
11300 Mathematical Systems Theory.
11400
11500 "Recent Developments in SAIL-An Algol Based Language for Artificial
11600 Intelligence", (with others). CS 308, Stanford University, August 1972.
11700 Proc. Fall Joint Computer Conference,Anaheim, Cal.,1972,p.1193-1202.
11800
11900 "Associative Languages" to appear in The Encyclopedia
12000 of Computer Science and Technology, A. Ralston, Ed.
12100
12200 "A Semantics-Based Decision Theoretic Region Analyzer" (with Y.Yakimovsky)
12300 Submitted to Third IJCAI, February,1973
12400
00100 MAJOR PROGRAMMING SYSTEMS DEVELOPED
00200
00300
00400
00500 TRANSLATOR WRITING SYSTEMS
00600
00700 FSL: Additional reference
00800
00900 Itturriaga, R. et.al., "Techniques and Advantages of Using the
01000 formal compiler writing system FSL to implement a Formula Algol
01100 Compiler", Proc. AFIPS Conference 1966, pp. 241-252.
01200
01300 VITAL: Additional Reference
01400
01500 Mondschein, L.F. "VITAL compiler-compiler System Reference Manual",
01600 TN-1967-12. M.I.T., Lincoln Lab., February 1967.
01700
01800
01900 ASSOCIATIVE LANGUAGE SYSTEMS
02000
02100 LEAP: Additional reference
02200
02300 Rovner, P., "The LEAP Users Manual", Mem. 23L-0009, M.I.T., Lincoln
02400 Lab., December 1968.
02500
02600 Swinehart, D. and R. Sproull, "SAIL Users Manual", Operating Note
02700 57.1; Stanford A.I. Project, April 1970.
02800
02900
03000 COOPERATING SEQUENTIAL PROCESSES
03100
03200 HAND-EYE SYSTEM: Additional reference
03300
03400 Pingle, K., "System Manual for Hand-Eye Hackers", Internal
03500 Memorandum, Stanford A.I. Project, June 1971.
00100 DOCTORAL STUDENTS
00200
00300
00400 NAME DEPT. TITLE/TOPIC FINAL ORAL CURRENTLY
00500
00600 F.J. Hilbing Industrial Strategies for 1968 U.S.A.F.
00700 Engineering Paging a Large Academy
00800 Associative Data Base
00900
01000 J.J. Horning Computer A Study of Grammati- 1969 U. of
01100 Science cal Inference Toronto
01200
01300 L.F. Morris Computer Semantic Models and 1969 Syracuse U.
01400 Science Compiler Correctness
01500
01600 G. Falk Computer Computer Interpreta- 1970 Rutgers U.
01700 Science tion of Imperfect
01800 Line Data as a Three-
01900 Dimensional Scene
02000
02100 I. Sobel Electrical Camera Models and 1970 Haifa
02200 Engineering Machine Perception Technion
02300
02400 J.Tenenbaum Electrical Accommodation in 1970 Stanford
02500 Engineering Computer Vision Research
02600 Institute
02700
02800 J.D.Becker Computer An Information 1970 Bolt,
02900 Science Processing Model of Beranek, &
03000 Intermediate Level Newman
03100 Cognition
03200
03300 R. Paul Computer Studies with a 1972 Stanford U.,
03400 Science Computer Controlled A.I. Lab.
03500 Arm
03600
03700 D.Swinehart Computer A One-Level Language 1972 Stanford U.,
03800 Science System A.I. Lab.
03900
04000 A. Gill Electrical Visual Feedback Con- 1972 Israel
04100 Engineering trol of a Mechanical Defense
04200 Arm Establshmnt.
04300
04400 D. Levine Computer Automated Error 1972 Stanford U.
04500 Science Correction of IMSSS
04600 German Sentences
04700
04800 G. Grape Computer Computer Vision 1973
04900 Science Through Sequential
05000 Abstraction
05100
05200 J. Gips Computer Structure of 1973
05300 Science Pictures Applied to
05400 Art and Vision
05500
05600 S.Ganapathy Computer Analysis of Simple 1973
05700 Science Scenes Using Multiple
05800 Views
05900
06000 J. Low Computer Optimization of 1973
06100 Science Data Structures for
06200 Associations
06300
06400 Y.Yakimovsky Computer Knowledge-based, 1973
06500 Science Decision Theoretic
06600 Region Analysis of
06700 Pictures
06800
00100 UNIVERSITY SERVICE
00200
00300
00400
00500 Freshman Seminar, "The Information Revolution" 1967-68
00600
00700 Faculty Senate 1969-70
00800
00900 Presidents Low-Cost Housing Committee 1968-69
01000
01100 Steering Committee, Junior Faculty Forum 1968-69
01200
01300 SWOPSI Seminar, "Computers and Society" 1969-70
01400
01500 Freshman Adviser 1971-72
01600
01700 Committee on Linguistics 1971-72
01800
01900 Lecturer, NSF Summer Program 1971
02000
02100 Faculty Adviser, Student Chapter,
02200 Association for Computing Machines 1966-68
02300
02400 Lecturer, Campus Alumni Conference - May 1970
02500
02600 Departmental Undergraduate Adviser 1972-73
02700
00100 Name: RICHARD P.C. PAUL
00200 Born: June 16, 1936 in Sydney Australia.
00300 Nationality: United States
00400 Marital Status: Married, two children.
00500
00600 EDUCATION:
00700 B.Eng. (Engineering Physics, with Honour) McGill 1963
00800 M.Sc. (Electrical Engineering) Stanford 1968
00900 Ph.D. (Computer Science) Stanford l972
01000
01100 PROFESSIONAL EXPERIENCE:
01200 Electronic Engineer, Stanford Linear Accelerator Center 1963-67
01300 Computer Systems Engineer, Stanford A.I. Laboratory 1967-68
01400 Research Programmer, Stanford A.I. Laboratory 1969-72
01500 Research Associate, Stanford A.I. Laboratory 1972-present
01600
01700 PUBLICATIONS:
01800
01900 "A Multi-pulse Generator for Testing a Radar Beacon", Canadian
02000 Engineering Journal, 1962.
02100
02200 With G. Falk and J. Feldman, "The Computer Representation of Simply
02300 Described Scenes" Memo AIM-101, Computer Science Dept., Stanford
02400 University, Stanford, California.
02500
02600 With Feldman et al, "The Use of Vision and Manipulation to Solve the
02700 Instant Insanity Puzzle", Proc. Second International Joint Conference
02800 on Artificial Intelligence.
02900
03000 "Trajectory Control of a Computer Arm", Proc. Second International
03100 Joint Conference on Artificial Intelligence, 1971.
03200
03300 "Modelling Trajectory Calculation and Servoing of a Computer
03400 Controlled Arm", PhD. Thesis, Computer Science Dept., Stanford
03500 University.
00100 Name: THOMAS O. BINFORD
00200 Born: April 13,1936, Jefferson Twp, Pennsylvania
00300 Nationality: USA
00400 Marital Status:divorced
00500
00600 EDUCATION:
00700 BS physics Pennsylvania State University 1957
00800 PhD physics University of Wisconsin 1965
00900
01000 CURRENT RESEARCH:
01100 Artificial Intelligence Laboratory, Stanford University
01200 laser depth ranging system
01300 representation of shape
01400 recognition of complex objects
01500 efficient method for proximity in n-dimensions
01600 color region analysis
01700 analysis of texture
01800 sensor study
01900
02000
02100 Artificial Intelligence Laboratory, MIT 1967-1970
02200 Topological region analysis
02300 line finder using sequential decision
02400 software for a visual experimentation
02500 recognition of parallelipipeds from incomplete line drawings
02600 two-dimensional shape recognition
02700 line verification
02800 line prediction
02900
03000 POST-DOCTORAL RESEARCH:
03100 Fulbright grant, Tata Institute of Fundamental Research,Bombay India
03200 partial wave analysis of hyperon production by pions;
03300 Regge-pole analysis of Sigma plus production by pions;
03400 theory of unstable particles and symmetry principles
03500
03600 PhD
03700 Strange particle production by pions near 1 Bev/c.
03800 Two new experimental equalities among cross sections;
03900 test of charge independence in hyperon production;
04000 showed adequacy of Regge-pole theory to explain high-energy cross sections;
04100
04200
04300 PUBLICATIONS:
04400
04500 "Structured Descriptions of Complex Objects",R.K.Nevatia and T.O.Binford
04600 Third Int Conf on AI, February, 1973.
04700 Stanford, Calif, 1973.
04800
04900 "Computer Vision", T.O.Binford and J.M.Tenenbaum, Computer, IEEE,
05000 April 1973.
05100
05200 "Sensor Systems for Manipulation", Conference on Remotely Manned
05300 Systems, JPL, Pasadena, Calif, Sept 1972.
05400
05500 "Visual Perception by Computer", Invited paper at IEEE Systems
05600 Science and Cybernetics, Miami, Dec 1971.
05700
05800 With G. Agin, "Representation and Description of Complex Objects", To
05900 be published.
06000
06100 With Feldman, et al, "The Use of Vision and Manipulation to Solve the
06200 Instant Insanity Puzzle", Proc. Second International Joint Conference
06300 on Artificial Intelligence.
06400
06500 With Tenenbaum, et al, "A laboratory for Hand-Eye Research",
06600 IFIP proceedings, August 1971.
06700
06800 "The Vision Laboratory-Part One", MIT AI memo 203.
06900
07000 "The TOPOLOGIST: A Region-Oriented System", (in draft form)
07100
07200 With A. Herskovits, "On Boundary Detection", MIT AI memo 183.
07300
07400 "Display Functions in LISP", MIT AI memo 182.
07500
07600 With Desai, "High Energy Elastic Scattering at Low Momentum Transfers", Physical
07700 Review 138,B1167.
07800
07900 With others, "Experimental Check of Some SU(6) Cross Section Equalities", Physical
08000 Review Letters 14,715.
08100
08200 With others, "Hyperon Production in Pion Interactions", Physical Review (1968).
08300
08400 "Triangle Inequality in Associated Production", Physical Review
08500 (1968).
08600 + - o
08700 With Anderson, et al, "CP-Nonconserving Decay K ← π π π ", Physical
08800 1
08900 Review Letters 14,475.
09000 o + - o
09100 With Stern, et al, "Absolute Decay Rate for K → π π π and the
09200 2
09300 2
09400 |DI|=1/2 Rule", Physical Review Letters 12,459.
09500
09600 With Lind, et al, "Experimental Investigation of V-A in Leptonic
09700 Lambda Decay", Phys Rev 135,B1483.
09800
09900
10000 DOCTORAL STUDENTS:
10100
10200 G.J.Agin Description and Representation 1972
10300 of Complex Objects
10400
10500 R.K.Nevatia Recognition of Complex Objects 1973
10600
10700 Ruzena Bajcsy (under Prof J. McCarthy)
10800 Computer Identification of Textured 1972
10900 Visual Scenes
11000
11100 T. Garvey Perceptual Problem Solving 1973
00100
00200 V. COMPUTING FACILITIES
00300
00400 The Laboratory operates a display-oriented timesharing system with
00500 facilities for real-time control of mechanical arms and other special
00600 devices. This system is connected to the ARPA computer network.
00700
00800 Central Processor: Digital Equipment Corporation PDP-10
00900
01000 Real-time Processor: Digital Equipment Corporation PDP-6
01100
01200 Network Processor: BBN IMP (Honeywell DDP-516)
01300
01400 Primary Store: 65K words of 1.7 microsecond DEC Core
01500 65K words of 1 microsecond Ampex Core
01600 131K words of 1.6 microsecond Ampex Core
01700
01800 Swapping Store: Librascope disk (5 million words, 22 million
01900 bits/second transfer rate)
02000
02100 File Store: IBM 3330 disc file, 6 spindles (leased)
02200
02300 Peripherals: 4 DECtape drives, 2 mag tape drives, line printer,
02400 Calcomp plotter, Xerox Graphics Printer
02500
02600 Terminals: 58 TV displays, 6 III displays, 3 IMLAC displays,
02700 1 ARDS display, 15 Teletype terminals
02800
02900 Special Equipment: Audio input and output systems, hand-eye
03000 equipment (2 TV cameras, 3 arms), remote-
03100 controlled cart
03200
03300 Nearly all of this equipment was acquired with support from the
03400 Advanced Research Projects Agency for research in artificial
03500 intelligence.
00100 VI. BUDGET
00105
00110
00115 Research in Robotics and Automation at the Stanford Artificial Intelligence
00120 Laboratory has been supported for several years by the Advanced Research
00125 Projects Agency of the Department of Defense. This support has supplied
00130 most of the necessary capital equipment and continues to support some of
00135 the basic work in this area. The budget requirements for our "proof of
00145 concept" proposal following this initial one year proposal will
00150 depend on the nature of ARPA support in the future.
00155
00160
00200
00300 ADVANCED AUTOMATION DEVELOPMENT
00400 RESEARCH GRANT PROPOSAL BUDGET
00500 ONE YEAR BEGINNING JULY 1, 1973
00600
00700
00800
00900 BUDGET CATEGORY
01000 7/1/73-7/1/74
01100 ----------------------------------------------------------------------
01200 A. SALARIES & WAGES:
01300
01400 1. Senior personnel:
01500
01600 a. Principal Investigator
01700 J. Feldman, Associate
01800 Professor, (2 mos. FTE) $ 3,624
01900
02000 b. Faculty Associate
02100 J. McCarthy, Professor ---
02150 Director of the Laboratory
02200
02300 2. Other Personnel:
02400
02500 a. Research Computer Scientist:
02600
02700 L. Earnest, (2 mos. FTE) 4,584
02800
02900 b. Research Associates:
03000
03100 T. Binford, (3 mos. FTE) 4,650
03200
03300 L. Paul, (3 mos. FTE) 4,410
03400
03500 c. Non-Fac. Professionals (other):
03600
03700 ------, Research Programmer,
03800 (12 mos. FTE) 12,000
03900
04000 V. Scheinman, Design Engineer,
04100 (6 mos. FTE) 8,280
04200
04300 d. Grad Students:
04400
04500 Student Research Assts.:
04600
04700 (2) 1/2 time Acad. Yr.,
04800 (9 mos. FTE) 6,120
04900
05000 (2) 100% Summer Qtr.,
05100 (6 mos. FTE.) 4,500
05200
05300 e. Secretarial-Clerical:
05400
05500 (1) Secretary, (6 mos. FTE) 3,900
05600
05700 f. Technical:
05800
05900 (1) Electronics Tech.,
06000 (12 mos. FTE) 9,600
06100
06200 g. Reserve for Salary Increases
06300 @ 5% per year 3,083
06400 ______
06500
06600 TOTAL SALARIES & WAGES $ 64,751
06700
06800 B. FRINGE BENEFITS:
06900
07000 16% 7/1/73 to 8/31/73,
07100 17.3% 9/1/73 to 6/30/74 11,062
07200 _______
07300
07400 Total Salaries, Wages and
07500 Fringe Benefits (A + B) $ 75,813
07600
07700 C. EXPENDABLE SUPPLIES AND EQUIP.:
07800
07900 Office Supplies, Xeroxing,
08000 Postage, Freight, Consulting,
08100 Honorariums 1,800
08200
08300 D. TRAVEL:
08400
08500 1. Domestic
08600 Local 600
08700 Other 3,600
08800 _____
08900 Total Travel 4,200
09000
09100 E. PUBLICATION COSTS: 400
09200
09300 F. OTHER COSTS:
09400
09500 1. Communications (telephones) 1,000
09600
09700 2. Equipment Rental (Disk) 15,000
09800 ------
09900 Total Other Costs 16,000
10000
10100 ______
10200 G. TOTAL DIRECT COSTS (A through F) $ 98,213
10300
10400 H. INDIRECT COSTS:
10500
10600 1. On Campus 46% of Net Total
10700 Direct Costs (G) 45,178
10800 ______
10900
11000 I. TOTAL COSTS (G + H) $143,391
11100 -------
11200 -------
00100 ADVANCED AUTOMATION DEVELOPMENT
00200 RESEARCH GRANT PROPOSAL BUDGET
00300 ONE YEAR BEGINNING JULY 1, 1973
00400
00500
00600
00700 BUDGET CATEGORY
00800 7/1/73-7/1/74
00900 ----------------------------------------------------------------------
01000 A. SALARIES & WAGES:
01100
01200 1. Senior personnel:
01300
01400 a. Principal Investigator
01500 J. Feldman, Associate
01600 Professor, (2 mos. FTE) $ 3,624
01700
01800 b. Faculty Associate
01900 J. McCarthy, Professor ---
02000
02100 2. Other Personnel:
02200
02300 a. Research Computer Scientist:
02400
02500 L. Earnest, (2 mos. FTE) 4,584
02600
02700 b. Research Associates:
02800
02900 T. Binford, (3 mos. FTE) 4,650
03000
03100 L. Paul, (3 mos. FTE) 4,410
03200
03300 c. Non-Fac. Professionals (other):
03400
03500 ------, Research Programmer,
03600 (12 mos. FTE) 12,000
03700
03800 V. Scheinman, Design Engineer,
03900 (6 mos. FTE) 8,280
04000
04100 d. Grad Students:
04200
04300 Student Research Assts.:
04400
04500 (2) 1/2 time Acad. Yr.,
04600 (9 mos. FTE) 6,120
04700
04800 (2) 100% Summer Qtr.,
04900 (6 mos. FTE.) 4,500
05000
05100 e. Secretarial-Clerical:
05200
05300 (1) Secretary, (6 mos. FTE) 3,900
05400
05500 f. Technical:
05600
05700 (1) Electronics Tech.,
05800 (12 mos. FTE) 9,600
05900
06000 g. Reserve for Salary Increases
06100 @ 5% per year 3,083
06200 ______
06300
06400 TOTAL SALARIES & WAGES $ 64,751
06500
06600 B. FRINGE BENEFITS:
06700
06800 16% 7/1/73 to 8/31/73,
06900 17.3% 9/1/73 to 6/30/74 11,062
07000 _______
07100
07200 Total Salaries, Wages and
07300 Fringe Benefits (A + B) $ 75,813
07400
07500 C. EXPENDABLE SUPPLIES AND EQUIP.:
07600
07700 Office Supplies, Xeroxing,
07800 Postage, Freight, Consulting,
07900 Honorariums 1,800
08000
08100 D. TRAVEL:
08200
08300 1. Domestic
08400 Local 600
08500 Other 3,600
08600 _____
08700 Total Travel 4,200
08800
08900 E. PUBLICATION COSTS: 400
09000
09100 F. OTHER COSTS:
09200
09300 1. Communications (telephones) 1,000
09400
09500 2. Equipment Rental (Disk) 15,000
09600 ------
09700 Total Other Costs 16,000
09800
09900 ______
10000 G. TOTAL DIRECT COSTS (A through F) $ 98,213
10100
10200 H. INDIRECT COSTS:
10300
10400 1. On Campus 46% of Net Total
10500 Direct Costs (G) 45,178
10600 ______
10700
10800 I. TOTAL COSTS (G + H) $143,391
10900 -------
11000 -------
00100 VII. REFERENCES
00200
00300 [Alexander] Tom Alexander, "The Hard Road to Soft Automation",
00400
00500 [Anderson 1972] R. Anderson,"Programmable Automation, The Future
00600 of Computers in Manufacturing", Datamation, Dec 1972.
00700
00800 [Agin] G. Agin, "Description and Representation of Curved Objects",
00900 Artificial Intelligence Laboratory, Stanford University, AIM-134,
01000 October 1972.
01100
01200
01300 [Bajcsy 1972] "Computer Identification of Visual Texture"
01400 AIM-180,Artificial Intelligence Laboratory, Stanford University,
01500 October 1972.
01600
01700 [Baumgart 1972a] B. Baumgart, "GEOMED - A Geometric Editor", May 1972.
01800 SAILON-68,Artificial Intelligence Lab, Stanford University,
01900
02000 [Baumgart 1972b] Baumgart, Bruce G., WINGED EDGE POLYHEDRON REPRESENTATION,
02100 AIM 179,Artificial Intelligence Lab, Stanford University,October 1972.
02200
02300 [Binford 1972]"Sensor Systems for Manipulation", Conference on Remotely
02400 Manned Systems, JPL, Pasadena, Calif, Sept 1972.
02500
02600 [Binford 1971] "Visual Perception by Computer", Invited paper IEEE
02700 Systems Science and Cybernetics, Miami, Dec 1971.
02800
02900 [Binford 1970] T.O.Binford, "Ranging by Laser", Internal Report,
03000 Artificial Intelligence Lab, Stanford University, Oct 1970.
03100
03200 Clowes, M.B.[1971] "On Seeing Things" AI Journal.
03300
03400 [Earnest 1967] L.D.Earnest,"Choosing an eye for a Computer";
03500 AI Memo 51, Artificial Intelligence Lab, Stanford University, 1967.
03600
03700 [Falk 1971] G. Falk, "Scene Analysis Based on Imperfect Edge Data", Proc. 2IJCAI,
03800 Brit. Comp. Soc., Sept. 1971.
03900
04000 [Feldman 1972] with others,"Recent Developments in SAIL-An Algol-Based
04100 Language for Artificial Intelligence", (with others).
04200 CS 308, Stanford University, August 1972.
04300 To appear in Proc. Fall Joint Computer Conference, 1972.
04400
04500 [Gill] Gill, Aharon, Visual Feedback and Related Problems in Computer-
04600 Controlled Hand Eye Coordination, AIM 178,October 1972.
04700
04800 [Grape 1969] "Computer Vision through Sequential Abstraction",
04900 Artificial Intelligence Laboratory, Internal Report, 1969.
05000
05100 [Grape 1970] "On predicting and Verifying Missing Elements in Line-Drawings"
05200 Artificial Intelligence Laboratory, Internal Report, March 1970.
05300
05305 [Grape 1973] "Computer Vision through Sequential Abstraction"
05310 Thesis, Computer Science Department, Stanford University, 1973.
05315
05400 Guzman, A. [1968] Computer recognition of three-dimensional objects
05500 in a visual scene. MAC-TR-59 (THESIS), Project MAC, Massachusetts
05600 Institute of Technology, Cambridge, Massachusetts, (December).
05700
05800 Horn, B.K.P.[1971] "The Binford-Horn Linefinder" MIT Vision Flash 16.
05900
06000 [Hueckel] M.H. Hueckel, "An Operator Which Locates Edges in Digitized
06100 Pictures", Stanford Artificial Intelligence Laboratory AIM-105,
06200 December 1969, JACM, Vol. 18, No. 1, January 1971.
06300
06400 Huffman, D.A. "Impossible objects as nonsense sentences" Machine
06500 Intelligence 6.
06600
06700 [Minsky 1972] "Artificial Intelligence Progress Report", AI Memo 252,
06800 MIT AI Lab, (1972);
06900
07000 [Nevatia 1973] R.K.Nevatia and T.O.Binford, "Structured Descriptions of
07100 Complex Objects", Submitted to Third IJCAI, February 1973.
07200
07300 [Paul] R. Paul, "Trajectory Control of a Computer Arm", 2nd
07400 International Joint Conference on Artificial Intelligence, 1971.
07500
07600 [Paul] R. Paul, "Modelling, Trajectory Calculation and Servoing of a
07700 Computer Controlled Arm", Ph.D. Thesis, Computer Science Dept.,
07800 Stanford University, Sept. 1972.
07900
08000 [Pingle 1972a] Karl K. Pingle, "Hand/Eye Library", Stanford
08100 Artificial Intelligence Laboratory Operating Note 35.1, January,
08200 1972.
08300
08400 [Pingle 1972b] K.K. Pingle and J.M. Tenenbaum, "An Accomodating Edge
08500 Follower", IJCAI-2. Proceedings of the 2nd. International Symposium
08600 on Industrial Robots, May 1972, Chicago, Illinois.
08700
08800 [Quam 1972] L. H. Quam, S. Liebes, Jr., R. B. Tucker, M. J. Hannah,
08900 B. G. Eross, "Computer Interactive Picture Processing", Stanford
09000 Artificial Intelligence Laboratory AIM-166, April 1972.
09100
09200 Roberts, L.G. [1963] Machine perception of three-dimensional solids.
09300 Technical Report No. 315, Lincoln Laboratory, M.I.T. (May)
09400 Also in Optical and Electro-Optical Information Proecesing,
09500 Tippett, J.T. et. al.(Eds.), MIT Press, Cambridge, Mass., 1965,
09600
09700 [Scheinman] V. D. Scheinman, Design of a Computer Manipulator,
09800 Stanford Artificial Intelligence Project, Memo AIM-92, June 1969.
09900
10000 [Sobel] Irwin Sobel, "Camera Models and Machine Perception", Stanford
10100 Artificial Intelligence Project Memo AIM-121, May, 1970.
10200
10300 [Shirai 1971a] "Recognition of Polyhedra with a Range Finder"
10400 Y. Shirai and M. Suwa, Internation Joint Conference on AI, London,
10500 Sept 1971.
10600
10700 [Shirai 1972] "A heterarchical program for Recognition of Polyhedra",
10800 Y. Shirai, Artificial Intelligence Laboratory, MIT, Memo 263.
10900
11000
11100 [Swinehart] D. Swinehart, R. Sproull, "SAIL", Stanford Artificial
11200 Intelligence Laboratory Operating Note 57, November 1969.
11300
11400 [Tenenbaum]
11500 J.M.Tenenbaum,"Accommodation in Computer Vision",
11600 Artificial Intelligence Lab, Stanford University, AIM-134 September 1970.
11700
11800 [Waltz] "Generating Semantic Descriptions from Drawings of Scenes
11900 with Shadows", D.L.Waltz, Artificial Intelligence Laboratory, MIT
12000 AI TR-271.
12100
12200
12300 [Yakimovsky 1972] Y.Yakimovsky and J.A.Feldman,
12400 "A Semantics-Based Decision Theoretic Region Analyzer"
12500 Submitted to Third IJCAI, February,1973
00100 VIII. RELEVANT LABORATORY PUBLICATIONS
00200
00300 The following articles published by members of the Stanford
00400 Artificial Intelligence Laboratory are relevant to this proposal.
00500
00600 J. McCarthy, "Computer Control of a Hand and Eye," in Proc. Third
00700 All-Union Conference on Automatic Control (Technical Cybernetics),
00800 Nauka, Moscow, 1967 (Russian).
00900
01000 J. Feldman (with D. Gries), "Translator Writing Systems", Comm. ACM,
01100 February 1968.
01200
01300 J. Feldman (with P. Rovner), "The Leap Language Data Structure",
01400 Proc. IFIP Congress, 1968.
01500
01600 J. McCarthy, L. Earnest, D. Reddy, and P. Vicens, "A Computer with
01700 Hands, Eyes, and Ears", Proc. AFIPS Conf. (FJCC), 1968.
01800
01900 K. Pingle, J. Singer, and W. Wichman, "Computer Control of a
02000 Mechanical Arm through Visual Input", Proc. IFIP Congress 1968.
02100
02200 J. Feldman, G. Feldman, G. Falk, G. Grape, J. Pearlman, I. Sobel, and
02300 J. Tenenbaum, "The Stanford Hand-Eye Project", Proc. International
02400 Conf. on Artificial Intelligence, Washington, D.C., 1969.
02500
02600 J. Feldman (with P. Rovner), "An Algol-based Associative
02700 Language", Comm. ACM, August 1969.
02800
02900 U. Montanari, "Continuous Skeletons from Digitized Images", JACM,
03000 October 1969.
03100
03200 R. Paul, G. Falk, J. Feldman, "The Computer Representation of Simply
03300 Described Scenes", Proc. 2ND Illinois Graphics Conference, Univ.
03400 Illinois, April 1969.
03500
03600 K. Pingle, "Visual Perception by a Computer", in Automatic
03700 Interpretation and Classification of Images, Academic Press, New
03800 York, 1970.
03900
04000 U. Montanari, "A Note on Minimal Length Polygonal Approximation to a
04100 Digitized Contour", Comm. ACM, January 1970.
04200
04300 U. Montanari, "On Limit Properties in Digitization Schemes", JACM,
04400 April 1970.
04500
04600 U. Montanari, "Separable Graphs, Planar Graphs and Web Grammars",
04700 Information and Control, May 1970.
04800
04900 U. Montenari, "Heuristically Guided Search and Chromosome Matching",
05000 J. Artificial Intelligence, Vol. 1, No. 4, December 1970.
05100
05200 G. Falk, "Scene Analysis Based on Imperfect Edge Data", Proc. 2IJCAI,
05300 Brit. Comp. Soc., Sept. 1971.
05400
05500 J. Feldman and R. Sproull, "System Support for the Stanford
05600 Hand-eye System", Proc. 2IJCAI, Brit. Comp. Soc., Sept. 1971.
05700
05800 J. Feldman, et al, "The Use of Vision and Manipulation to Solve the
05900 `Instant Insanity' Puzzle", Proc. 2IJCAI, Brit. Comp. Soc., Sept.
06000 1971.
06100
06200 M. Hueckel, "An Operator which Locates Edges in Digitized Pictures",
06300 JACM, January 1971.
06400
06500 M. Kahn and B. Roth, "The Near-minimum-time Control of Open-loop
06600 Articulated Kinematic Chains", Trans. ASME, Sept. 1971.
06700
06800 U. Montanari, "On the Optimal Detection of Curves in Noisy Pictures",
06900 Comm. ACM, May 1971.
07000
07100 N. Nilsson, "Problem-solving Methods in Artificial Intelligence",
07200 McGraw-Hill, New York, 1971.
07300
07400 R. Paul, "Trajectory Control of a Computer Arm", Proc. 2IJCAI, Brit.
07500 Comp. Soc., Sept. 1971.
07600
07700 K. Pingle and J. Tenenbaum, "An Accomodating Edge Follower", Proc.
07800 2IJCAI, Brit. Comp. Soc., Sept. 1971.
07900
08000 B. Roth, "Design, Kinematics, and Control of Computer-controlled
08100 Manipulators", Proc. 6th All Union Conference on New Problems in
08200 Theory of Machines & Mechanics, Leningrad, Jan. 1971 (in press).
08300
08400 J. Tenenbaum, et, al, "A Laboratory for Hand-eye Research", Proc.
08500 IFIP Congress 1971.
08600
08700 G. Falk, "Interpretation of Imperfect Line Data as a
08800 Three-Dimensional Scene", J. Artificial Intelligence, Vol. 3, No. 2,
08900 1972.
09000
09100 J. Gips, "A New Reversible Figure", Perceptual & Motor Skills, 34,
09200 306, 1972.
09300
00100 IX. FILMS
00200
00300 Prints of the following films are available for short-term loan.
00400
00500 1. Art Eisenson and Gary Feldman, "Ellis D. Kroptechev and Zeus, his
00600 Marvelous Time-Sharing System", 16mm black and white with
00700 sound, 15 minutes, March 1967.
00800
00900 The advantages of time-sharing over standard batch processing are
01000 revealed through the good offices of the Zeus time-sharing system on
01100 a PDP-1 computer. Our hero, Ellis, is saved from a fate worse than
01200 death. Recommended for mature audiences only.
01300
01400 2. Gary Feldman, "Butterfinger", 16mm color with sound, 8 minutes,
01500 March 1968.
01600
01700 Describes the state of the hand-eye system at the Artificial
01800 Intelligence Project in the fall of 1967. The PDP-6 computer getting
01900 visual information from a television camera and controlling an
02000 electrical-mechanical arm solves simple tasks involving stacking
02100 blocks. The techniques of recognizing the blocks and their positions
02200 as well as controlling the arm are briefly presented. Rated "G".
02300
02400 3. Raj Reddy, Dave Espar and Art Eisenson, "Hear Here", 16mm color
02500 with sound, 15 minutes, March 1969.
02600
02700 Describes the state of the speech recognition project as of Spring,
02800 1969. A discussion of the problems of speech recognition is followed
02900 by two real time demonstrations of the current system. The first
03000 shows the computer learning to recognize phrases and second shows how
03100 the hand-eye system may be controlled by voice commands. Commands as
03200 complicated as "Pick up the small block in the lower lefthand
03300 corner", are recognized and the tasks are carried out by the computer
03400 controlled arm.
03500
03600 4. Gary Feldman and Donald Peiper, "Avoid", 16mm silent, color, 5
03700 minutes, March 1969.
03800
03900 Reports on a computer program written by D. Peiper for his Ph.D.
04000 Thesis. The problem is to move the computer controlled
04100 electrical-mechanical arm through a space filled with one or more
04200 known obstacles. The program uses heuristics for finding a safe
04300 path; the film demonstrates the arm as it moves through various
04400 cluttered environments with fairly good success.
04500
04600 5. Richard Paul and Karl Pingle, "Instant Insanity", 16 mm color,
04700 silent, 6 minutes, August, 1971.
04800
04900 Shows the hand/eye system solving the puzzle "Instant Insanity".
05000 Sequences include finding and recognizing cubes, color recognition
05100 and object manipulation. This film was made to accompany a paper
05200 presented at the 1971 International Joint Conference on Artificial
05300 Intelligence in London. It may be hard to understand without a
05400 narrator.
05500
05600 6. Suzanne Kandra, "Motion and Vision", 16 mm color, sound, 22
05700 minutes, November 1972.
05800
05900 A technical presentation of three research projects completed in
06000 1972: advanced arm control by R. P. Paul [AIM-177], visual feedback
06100 control by A. Gill [AIM-178], and representation and description of
06200 curved objects by G. Agin [AIM-173].
00100 X. RECENT REPORTS
00200
00300 The following reports have been published by the Stanford Artificial
00400 Intelligence Laboratory since 1971.
00500
00600
00700 AIM-140, Roger C. Schank, INTENTION, MEMORY, AND COMPUTER
00800 UNDERSTANDING, January 1971, 59 pages.
00900
01000 Procedures are described for discovering the intention of a speaker
01100 by relating the Conceptual Dependence representation of the speaker's
01200 utterance to the computer's world model such that simple implications
01300 can be made. These procedures function at levels higher than that of
01400 structure of the memory. Computer understanding of natural language
01500 is shown to consist of the following parts: assigning a conceptual
01600 representation to an input; relating that representation to the
01700 memory such as to extract the intention of the speaker; and selecting
01800 the correct response type triggered by such an utterance according to
01900 the situation.
02000
02100 AIM-141, Bruce G. Buchanan, Edward A. Feigenbaum, and Joshua
02200 Lederberg, THE HEURISTIC DENDRAL PROGRAM FOR EXPLAINING
02300 EMPIRICAL DATA, February 1971, 20 pages.
02400
02500 The Heuristic DENDRAL program uses an information processing model of
02600 scientific reasoning to explain experimental data in organic
02700 chemistry. This report summarizes the organization and results of the
02800 program for computer scientists. The program is divided into three
02900 main parts: planning, structure generation, and evaluation.
03000
03100 The planning phase infers constraints on the search space from the
03200 empirical data input to the system. The structure generation phase
03300 searches a tree whose termini are models of chemical models using
03400 pruning heuristics of various kinds. The evaluation phase tests the
03500 candidate structures against the original data. Results of the
03600 program's analyses of some tests are discussed.
03700
03800 AIM-142, Robin Milner, AN ALGEBRAIC DEFINITION OF SIMULATION BETWEEN
03900 PROGRAMS, February 1971, 21 pages.
04000
04100 A simulation relation between programs is defined which is
04200 quasi-ordering. Mutual simulation is then an equivalence relation,
04300 and by dividing out by it we abstract from a program such details as
04400 how the sequencing is controlled and how data is represented. The
04500 equivalence classes are approximations to the algorithms which are
04600 realized, or expressed, by their member programs.
04700
04800 A technique is given and illustrated for proving simulation and
04900 equivalence of programs; there is an analogy with Floyd's technique
05000 for proving correctness of programs. Finally, necessary and
05100 sufficient conditions for simulation are given.
05200
05300 AIM-143. John McCarthy, Arthur Samuel and Artificial Intelligence
05400 Project staff, Edward Feigenbaum and Heuristic Dendral
05500 Project staff, Project Technical Report, MARCH 1971, 80 pages.
05600 (out of print).
05700
05800 An overview is presented of current research at Stanford in
05900 artificial intelligence and heuristic programming. This report is
06000 largely the text of a proposal to the Advanced Research Projects
06100 Agency for fiscal years 1972-3.
06200
06300 AIM-144. Lynn H. Quam, COMPUTER COMPARISON OF PICTURES, May 1971,
06400 120 pages.
06500
06600 This dissertation reports the development of digital computer
06700 techniques for detecting changes in scenes by normalizing and
06800 comparing pictures which were taken from different camera positions
06900 and under different conditions of illumination. The pictures are
07000 first geometrically normalized to a common point of view. Then they
07100 are photometrically normalized to eliminate the differences due to
07200 different illumination, camera characteristics, and reflectance
07300 properties of the scene due to different sun and view angles. These
07400 pictures are then geometrically registered by maximizing the cross
07500 correlation between areas in them. The final normalized and
07600 registered pictures are then differenced point by point.
07700
07800 The geometric normalization techniques require relatively accurate
07900 geometric models for the camera and the scene, and static spatial
08000 features must be present in the pictures to allow precise geometric
08100 alignment using the technique of cross correlation maximization.
08200
08300 Photometric normalization also requires a relatively accurate model
08400 for the photometric response of the camera, a reflectance model for
08500 the scene (reflectance as a function of the illumination view, and
08600 phase angles) and some assumptions about the kinds of reflectance
08700 changes which are to be detected.
08800
08900 These techniques have been incorporated in a system for comparing
09000 Mariner 1971 pictures of Mars to detect variable surface phenomena as
09100 well as color and polarization differences. The system has been
09200 tested using Mariner 6 and 7 pictures of Mars.
09300
09400 Although the techniques described in this dissertation were developed
09500 for Mars pictures, their use is not limited to this application.
09600 Various parts of this software package, which was developed for
09700 interactive use on the time-sharing system of the Stanford Artificial
09800 Intelligence Project, are currently being applied to other scenery.
09900
10000
10100 AIM-145, Bruce G. Buchanan, Edward A. Feigenbaum, and Joshua
10200 Lederberg, A HEURISTIC PROGRAMMING STUDY OF THEORY FORMATION
10300 IN SCIENCE, June 1971, 41 pages.
10400
10500 The Meta-DENDRAL program is a a vehicle for studying problems of
10600 theory formation in science. The general strategy of Meta-DENDRAL is
10700 to reason from data to plausible generalizations and then to organize
10800 the generalizations into a unified theory. Three main subproblems
10900 are discussed: (1) explain the experimental data for each individual
11000 chemical structure, (2) generalize the results from each structure to
11100 all structures, and (3) organize the generalizations into a unified
11200 theory. The program is built upon the concepts and programmed
11300 routines already available in the Heuristic DENDRAL performance
11400 program, but goes beyond the performance program in attempting to
11500 formulate the theory which the performance program will use.
11600
11700
11800 AIM-146, Andrei P. Ershov, PARALLEL PROGRAMMING, July 1971, 14 pages.
11900
12000 This report is based on lectures given at Stanford University by Dr.
12100 Ershov in November, 1970.
12200
12300
12400 AIM-147, Robert E. Kling, REASONING BY ANALOGY WITH APPLICATIONS TO
12500 HEURISTIC PROBLEM SOLVING: A CASE STUDY, August 1971,
12600 191 pages.
12700
12800 An information-processing approach to reasoning by analogy is
12900 developed that promises to increase the efficiency of heuristic
13000 deductive problem-solving systems. When a deductive problem-solving
13100 system accesses a large set of axioms more than sufficient particular
13200 problem, it will often create many irrelevant deductions than
13300 saturate the memory of the problem solver.
13400
13500 Here, an analogy with some previously solved problem and a new
13600 unsolved problem is used to restrict the data base to a small set of
13700 appropriate axioms. This procedure (ZORBA) is studied in detail for
13800 a resolution theorem proving system. A set of algorithms (ZORBA-I)
13900 which automatically generates an analogy between a new unproved
14000 theorem, T↓A, and a previously proved theorem, T, is described in
14100 detail. ZORBA-I is implemented in LISP on a PDP-10.
14200
14300 ZORBA-I is examined in terms of its empirical performance on parts of
14400 analogous theorems drawn from abstract algebra. Analytical studies
14500 are included which show that ZORBA-I can be useful to aid automatic
14600 theorem proving in many pragmatic cases while it may be a detriment
14700 in certain specially contrived cases.
14800
14900
15000 AIM-148, Edward Ashcroft, Zohar Manna, and Amir Pneuli, DECIDABLE
15100 PROPERTIES OF MONADIC FUNCTIONAL SCHEMAS, July 1971,
15200 10 pages.
15300
15400 We define a class of (monadic) functional schemas which properly
15500 include `Ianov' flowchart schemas. We show that the termination,
15600 divergence and freedom problems for functional schemas are decidable.
15700 Although it is possible to translate a large class of non-free
15800 functional schemas into equivalent free functional schemas, we show
15900 that this cannot be done in general. We show also that the
16000 equivalence problem for free functional schemas is decidable. Most
16100 of the results are obtained from well-known results in Formal
16200 Languages and Automata Theory.
16300
16400
16500 AIM-149, Rodney Albert Schmidt, Jr., A STUDY OF THE REAL-TIME CONTROL
16600 OF A COMPUTER-DRIVEN VEHICLE, August 1971, 180 pages.
16700
16800 Vehicle control by the computer analysis of visual images is
16900 investigated. The areas of guidance, navigation, and incident
17000 avoidance are considered. A television camera is used as the prime
17100 source of visual image data.
17200
17300 In the guidance system developed for an experimental vehicle, visual
17400 data is used to gain information about the vehicle system dynamics,
17500 as well as to guide the vehicle. This information is used in real
17600 time to improve performance of the non-linear, time-varying vehicle
17700 system.
17800
17900 A scheme for navigation by pilotage through the recognition of two
18000 dimensional scenes is developed. A method is proposed to link this
18100 to a computer-modelled map in order to make journeys.
18200
18300 Various difficulties in avoiding anomolous incidents in the automatic
18400 control of automobiles are discussed, together with suggestions for
18500 the application of this study to remote exploration vehicles or
18600 industrial automation.
18700
18800
18900 AIM-150, Robert W. Floyd, TOWARD INTERACTIVE DESIGN OF CORRECT
19000 PROGRAMS, September 1971, 12 pages.
19100
19200 We propose an interactive system proving the correctness of a
19300 program, or locating errors, as the program is designed.
19400
19500 AIM-151, Ralph L. London, CORRECTNESS OF TWO COMPILERS FOR A LISP
19600 SUBSET, October 1971, 41 pages.
19700
19800 Using mainly structural induction, proofs of correctness of each of
19900 two running Lisp compilers for the PDP-10 computer are given.
20000 Included are the rationale for presenting these proofs, a discussion
20100 of the proofs, and the changes needed to the second compiler to
20200 complete its proof.
20300
20400
20500 AIM-152, A.W. Biermann, ON THE INFERENCE OF TURING MACHINES FROM
20600 SAMPLE COMPUTATIONS, October 1971, 31 pages.
20700
20800 An algorithm is presented which when given a complete description of
20900 a set of Turing machine computations finds a Turing machine which is
21000 capable of doing those computations. This algorithm can serve as the
21100 basis for designing a trainable device which can be trained to
21200 simulate any Turing machine by being led through a series of sample
21300 computations done by that machine. A number of examples illustrate
21400 the use of the technique and the possibility of the application to
21500 other types of problems.
21600
21700
21800 AIM-153, Patrick J. Hayes, THE FRAME PROBLEM AND RELATED PROBLEMS IN
21900 ARTIFICIAL INTELLIGENCE, November 1971, 18 pages.
22000
22100 The frame problem arises in considering the logical structure of a
22200 robot's beliefs. It has been known for some years, but only recently
22300 has much progress been made. The problem is described and discussed.
22400 Various suggested methods for its solution are outlines, and
22500 described in a uniform notation. Finally, brief consideration is
22600 given to the problem of adjusting a belief system in the face of
22700 evidence which contradicts beliefs. It is shown that a variation on
22800 the situation notation of (McCarthy and Hayes, 1969) permits an
22900 elegant approach, and relates this problem to the frame problem.
23000
23100
23200 AIM-154, Zohar Manna, Stephen Ness and Jean Vuillemin, INDUCTIVE
23300 METHODS FOR PROVING PROPERTIES OF PROGRAMS, November 1971,
23400 24 pages.
23500
23600 We have two main purposes in this paper. First, we clarify and
23700 extend known results about computation of recursive programs,
23800 emphasizing the difference between the theoretical and practical
23900 approaches. Secondly, we present and examine various known methods
24000 for proving properties of recursive programs. We discuss in detail
24100 two powerful inductive methods, computational induction and
24200 structural induction, illustrating their applications by various
24300 examples. We also briefly discuss some other related methods.
24400
24500 Our aim in this work is to introduce inductive methods to as wide a
24600 class of readers as possible and to demonstrate their power as
24700 practical techniques. We ask the forgiveness of our more
24800 theoretical-minded colleagues for our occasional choice of clarity
24900 over precision.
25000
25100
25200 AIM-155, Jonathan Leonard Ryder, HEURISTIC ANALYSIS OF LARGE TREES AS
25300 GENERATED IN THE GAME OF GO, December 1971, 300 pages.
25400
25500 The Japanese game of Go is of interest both as a problem in
25600 mathematical repesentation and as a game which generates a move tree
25700 with an extraordinarily high branching factor (100 to 300 branches
25800 per ply). The complexity of Go (and the difficulty of Go for human
25900 players) is thought to be considerably greater than that of chess.
26000 The constraints of being able to play a complete game and of being
26100 able to produce a move with a moderate amount of processing time were
26200 placed on the solution.
26300
26400 The basic approach used was to find methods for isolating and
26500 exploring several sorts of relevant subsections of the global game
26600 tree. This process depended heavily on the ability to define and
26700 manipulate the entities of Go as recursive functions rather than as
26800 patterns of stones. A general machine-accessible theory of Go was
26900 developed to provide context for program evaluations.
27000
27100 A program for playing Go is now available on the Stanford PDP-10
27200 computer. It will play a complete game, taking about 10 to 30
27300 seconds for an average move. The quality of play is better than that
27400 of a beginner in many respects, but incompletenesses in the current
27500 machine-representable theory of Go prevent the present program from
27600 becoming a strong player.
27700
27800
27900 AIM-156, Kenneth Mark Colby, Franklin Dennis Hilf, Sylvia Weber, and
28000 Helena C. Kraemer, A RESEMBLANCE TEST FOR THE VALIDATION
28100 OF A COMPUTER SIMULATION OF PARANOID PROCESSES,
28200 November 1971, 29 pages.
28300
28400 A computer simulation of paranoid processes in the form of a dialogue
28500 algorithm was subjected to a validation study using an experimental
28600 resemblance test in which judges rate degrees of paranoia present in
28700 initial psychiatric interviews of both paranoid patients and of
28800 versions of the paranoid model. The statistical results indicate a
28900 satisfactory degree of resemblance between the two groups of
29000 interviews. It is concluded that the model provides a successful
29100 simulation of naturally occuring paranoid processes.
29200
29300
29400 AIM-157, Yorick Wilks, ONE SMALL HEAD----SOME REMARKS ON THE USE OF
29500 `MODEL' IN LINGUISTICS, December 1971, 17 pages.
29600
29700 I argue that the present situation in formal linguistics, where much
29800 new work is presented as being a "model of the brain", or of "human
29900 language behavior", is an undesirable one. My reason for this
30000 judgement is not the conservative (Braithwaitian) one that the
30100 entities in question are not really models but theories. It is
30200 rather that they are called models because they cannot be theories of
30300 the brain at the present stage of brain research, and hence that the
30400 use of "model" in this context is not so much aspirational as
30500 resigned about our total ignorance of how the brain stores and
30600 processes linguistic information. The reason such explanatory
30700 entities cannot be theories is that this ignorance precludes any
30800 "semantic ascent" up the theory; i.e., interpreting the items of the
30900 theory in terms of observables. And the brain items, whatever they
31000 may be, are not, as Chomsky has sometimes claimed, in the same
31100 position as the "occult entities" of Physics like Gravitation; for
31200 the brain items are not theoretically unreachable, merely unreached.
31300
31400 I then examine two possible alternate views of what linguistic
31500 theories should be proffered as theories of: theories of sets of
31600 sentences, and theories of a particular class of algorithms. I argue
31700 for a form of the latter view, and that its acceptance would also
31800 have the effect of making Computational Linguistics a central part of
31900 Linguistics, rather than the poor relation it is now.
32000
32100 I examine a distinction among "linguistic models" proposed recently
32200 by Mey. who was also arguing for the self-sufficiency of
32300 Computational Linguistics, though as a "theory of performance". I
32400 argue that his distinction is a bad one, partly for the reasons
32500 developed above and partly because he attempts to tie it to Chomsky's
32600 inscrutable competance-performance distinction. I conclude that the
32700 independence and self-sufficiency of Computational Linguistics are
32800 better supported by the arguments of this paper.
32900
33000
33100 AIM-158, Zohar Manna, Ashok Chandra, PROGRAM SCHEMAS WITH EQUALITY,
33200 December 1971, 22 pages.
33300
33400 We discuss the class of program schemas augmented with equality
33500 tests, that is, tests of equality between terms. In the first part
33600 of the paper we illustrate the "power" of equality tests. It turns
33700 out that the class of program schemas with equality is more powerful
33800 than the "maximal" classes of schemas suggested by other
33900 investigators. In the second part of the paper, we discuss the
34000 decision problems of program schemas with equality. It is shown, for
34100 example, that while the decision problems normally considered for
34200 schemas (such as halting, divergence, equivalence, isomorphism and
34300 freedom) are decidable for ianov schemas. They all become
34400 undecidable if general equality tests are added. We suggest,
34500 however, limited equality tests which can be added to certain
34600 subclasses of program schemas while preserving their decidability
34700 property.
34800
34900
35000 AIM-159, J.A. Feldman and Paul C. Shields, TOTAL COMPLEXITY AND
35100 INFERENCE OF BEST PROGRAMS, April 1972.
35200
35300 Axioms for a total complexity measure for abstract programs are
35400 presented. Essentially, they require that total complexity be an
35500 unbounded increasing function of the Blum time and size measures.
35600 Algorithms for finding the best program on a finite domain are
35700 presented, and their limiting behavior for infinite domains
35800 described. For total complexity, there are important senses in which
35900 a machine can find the best program for a large class of functions.
36000
36100
36200 AIM-160, J. Feldman, AUTOMATIC PROGRAMMING, February 1972, 20 pages.
36300
36400 The revival of interest in Automatic Programming is considered. The
36500 research is divided into direct efforts and theoretical developments
36600 and the successes and prospects of each are described.
36700
36800
36900 AIM-161, Y. Wilks, AN ARTIFICIAL INTELLIGENCE APPROACH TO MACHINE
37000 TRANSLATION, February 1972, 44 pages.
37100
37200 The paper describes a system of semantic analysis and generation,
37300 programmed in LISP 1.5 and designed to pass from paragraph length
37400 input in English to French via an interlingual representation. A
37500 wide class of English input forms will be covered, but the vocabulary
37600 will initially be restricted to one of a few hundred words. With
37700 this subset working, and during the current year (1971-72), it is
37800 also hoped to map the interlingual representation onto some predicate
37900 calculus notation so as to make possible the answering of very simple
38000 questions about the translated matter. The specification of the
38100 translation system itself is complete, and its main points are:
38200 i) It translates phrase by phrase--with facilities for reordering
38300 phrases and establishing essential semantic connectivities between
38400 them--by mapping complex semantic stuctures of "message" onto each
38500 phrase. These constitute the interlingual representation to be
38600 translated. This matching is done without the explicit use of a
38700 conventional syntax analysis, by taking as the appropriate matched
38800 structure the "most dense" of the alternative structures derived.
38900 This method has been found highly successful in earlier versions of
39000 this analysis system.
39100
39200 ii) The French output strings are generated without the explicit use
39300 of a generative grammar. That is done by means of STEREOTYPES:
39400 strings of French words, and functions evaluating to French words,
39500 which are attached to English word senses in the dictionary and built
39600 into the interlingual representation by the analysis routines. The
39700 generation program thus receives an interlingual representation that
39800 already contains both French output and implicit procedures for
39900 assembling the output, since the stereotypes are in effect recursive
40000 procedures specifying the content and production of the output word
40100 strings. Thus the generation program at no:time consults a word
40200 dictionary or inventory of grammar rules.
40300
40400 It is claimed that the system of notation and translation described
40500 is a convenient one for expressing and handling the items of semantic
40600 information that are ESSENTIAL to any effective MT system. I discuss
40700 in some detail the semantic information needed to ensure the correct
40800 choice of output prepositions in French; a vital matter inadequately
40900 treated by virtually all previous formalisms and projects.
41000
41100
41200 AIM-162, Roger Schank, Neil Goldman, Chuck Reiger, Chris Reisbeck,
41300 PRIMITIVE CONCEPTS UNDERLYING VERBS OF THOUGHT,
41400 April 1972, 102 pages.
41500
41600 In order to create conceptual structures that will uniquely and
41700 unambiguously represent the meaning of an utterance, it is necessary
41800 to establish `primitive' underlying actions and states into which
41900 verbs can be mapped. This paper presents analyses of the most common
42000 mental verbs in terms of such primitive actions and states. In order
42100 to represent the way people speak about their mental processes, it
42200 was necessary to add to the usual ideas of memory structure the
42300 notion of Immediate Memory. It is then argued that there are only
42400 three primitive mental ACTs.
42500
42600
42700 AIM-163, J.M. Cadiou, RECURSIVE DEFINITIONS OF PARTIAL FUNCTIONS AND
42800 THEIR COMPUTATIONS, April 1972, 160 pages.
42900
43000 A formal syntactic and semantic model is presented for `recursive
43100 definitions' which are generalizations of those found in LISP, for
43200 example. Such recursive definitions can have two classes of
43300 fixpoints, the strong fixpoints and the weak fixpoints, and also
43400 possess a class of computed partial functions.
43500
43600 Relations between these classes are presented: fixpoints are shown
43700 to be extensions of computed functions. More precisely, strong
43800 fixpoints are shown to be extensions of computed functions when the
43900 computations may involve "call by name" substitutions; weak
44000 fixpoints are shown to be extensions of computed functions when the
44100 computation only involve "call by value" substitutions. The
44200 Church-Rosser property for recursive definitions with fixpoints also
44300 follows from these results.
44400
44500 Then conditions are given on the recursive definitions to ensure that
44600 they possess least fixpoints (of both classes), and computation rules
44700 are given for computing these two fixpoints: the "full" computation
44800 rule, which leads to the least weak fixpoint. A general class of
44900 computation rules, called `safe innermost', also lead to the latter
45000 fixpoint. The "leftmost innermost" rule is a special case of those,
45100 for the LISP recursive definitions.
45200
45300
45400 AIM-164, Zohar Manna and Jean Vuillemin, FIXPOINT APPROACH TO THE
45500 THEORY OF COMPUTATION, April 1972, 29 pages.
45600
45700 Substantial effort has been put into finding verification techniques
45800 for computer programs. There are now so many verification techniques
45900 that a choice in a practical situation may appear difficult to the
46000 non-specialist. In particular, the most widely used methods, such as
46100 the "inductive assertion method", can be used to prove some
46200 input-output relation (assuming that the program terminates) while
46300 such problems as termination or equivalence usually require a
46400 different type of technique.
46500
46600 Our main purpose in this paper is to suggest that Scott's fixedpoint
46700 approach to the semantics of programming languages frees us from that
46800 dilemma. It allows one not only to justify all existing verification
46900 techniques, but also to extend them to handle other properties of
47000 computer programs, including termination and equivalence, in a
47100 uniform manner.
47200
47300 AIM-165, D,A, Bochvar, TWO PAPERS ON PARTIAL PREDICATE CALCULUS,
47400 April 1972, 50 pages.
47500
47600 The three-valued system to which this study is devoted is of interest
47700 as a logical calculus for two reasons: first, it is based on
47800 formalization of certain basic and intuitively obvious relations
47900 satisfied by the predicates "true", "false" and "meaningless" as
48000 applied to propositions, and as a result the system possesses a
48100 clear-cut and intrinsically logical interpretation; second, the
48200 system provides a solution to a specifically logical problem,
48300 analysis of the paradoxes of classical mathematical logic, by
48400 formally proving that certain propositions are meaningless.
48500
48600 The paper consists of three parts. In the first we develop the
48700 elementary part of the system--the propositional calculus--on the
48800 basis of intuitive considerations. In the second part we outline the
48900 "restricted" functional calculus corresponding to the propositional
49000 calculus. The third and last part uses a certain "extension" of the
49100 functional calculus to analyze the paradoxes of classical
49200 mathematical logic.
49300
49400 We are indebted to Professor V.I. Glivenko for much valuable advice
49500 and criticism. In particular, he provided a more suitable definition
49600 of the function a(see I, Section 2, subsection 1.).
49700
49800 AIM 166, Lynn H. Quam, Sidney Liebes, Jr., Robert B. Tucker, Marsha
49900 Jo Hannah, Botond G. Eross, COMPUTER INTERACTIVE PICTURE
50000 PROCESSING, April 1972, 40 pages.
50100
50200 This report describes work done in image processing using an
50300 interactive computer system. Techniques for image differencing are
50400 described and examples using images returned from Mars by the Mariner
50500 Nine spacecraft are shown. Also described are techniques for stereo
50600 image processing. Stereo processing for both conventional camera
50700 systems and the Viking 1975 Lander camera system is reviewed.
50800
50900 AIM-167, Ashok Chandra, EFFICIENT COMPILATION OF LINEAR RECURSIVE
51000 PROGRAMS, June 1972, 43 pages.
51100
51200 We consider the class of linear recursive programs. A linear
51300 recursive program is a set of procedures where each procedure can
51400 make at most one recursive call. The conventional stack
51500 implementation of recursion requires time and space both proportional
51600 to n, the depth of recursion. It is shown that in order to
51700 implement linear recursion so as to execute in time n one doesn't
51800 need space proportional to n: n**ε for sufficiently small ε will do.
51900 It is also known that with constant space one can implement linear
52000 recursion in time n**2. We show that one can do much better:
52100 n**(1+ε) for arbitrarily small ε. We also describe an algorithm that
52200 lies between these two: it takes time n*log n and space log n.
52300
52400 It is shown that several problems are closely related to the linear
52500 recursion problem, for example, the problem of reversing an input
52600 tape given a finite automaton with several one-way heads. By casting
52700 all these problems into canonical form, efficient solutions are
52800 obtained simultaneously for all.
52900
53000 AIM-168, Shigeru Igarashi, ADMISSIBILITY OF FIXED-POINT INDUCTION IN
53100 FIRST-ORDER LOGIC OF TYPED THEORIES, May 1972, 40 pages.
53200
53300 First-order logic is extended so as to deal with typed theories,
53400 especially that of continuous functions with fixed-point induction
53500 formalized by D. Scott. The translation of his formal system, or the
53600 λ calculus-oriented system derived and implemented by R. Milner, into
53700 this logic amounts to adding predicate calculus features to them.
53800
53900 In such a logic the fixed-point induction axioms are no longer valid,
54000 in general, so that we characterize formulas for which Scott-type
54100 induction is applicable, in terms of syntax which can be checked
54200 by machines automatically.
54300
54400 Diskfile: Aim168.igr[aim,doc.)
54500
54600 AIM-169, Robin Milner, LOGIC FOR COMPUTABLE FUNCTIONS. DESCRIPTION
54700 OF A MACHINE IMPLEMENTATION, May 1972, 36 pages.
54800
54900 This paper is primarily a user's manual for LCF, a proof-checking
55000 program for a logic of computable functions proposed by Dana Scott in
55100 1969, but unpublished by him. We use the name LCF also for the logic
55200 itself, which is presented at the start of the paper. The
55300 proof-checking program is designed to allow the user interactively to
55400 generate formal proofs about computable functions and functionals
55500 over a variety of domains, including those of interest to the
55600 computer scientist--for example, integers, lists and computer
55700 programs and their semantics. The user's task is alleviated by two
55800 features: a subgoaling facility and a powerful simplification
55900 mechanism. Applications include proofs of program correctness and in
56000 particular of compiler correctness; these applications are not
56100 discussed herein, but are illustrated in the papers referenced in the
56200 introduction.
56300
56400 Diskfile: Lcfman.rgm[aim,doc]
56500
56600 AIM-170, Yorick Wilks, LAKOFF ON LINGUISTICS AND NATURAL LOGIC,
56700 June 1972, 19 pages.
56800
56900 The paper examines and criticises Lakoff's notions of a natural logic
57000 and of a generative semantics described in terms of logic, I argue
57100 that the relationship of these notions to logic as normally
57200 understood is unclear, but I suggest, in the course of the paper, a
57300 number of possible interpretations of his thesis of generative
57400 semantics. I argue further that on these interpretations a mere
57500 notational variant of Chomskyan theory, I argue, too, that Lakoff's
57600 work may provide a service in that it constitutes a reductio ad
57700 absurdum of the derivational paradigm of modern linguistics; and
57800 shows, inadvertently, that only a system with the ability to
57900 reconsider its own inferences can do the job that Lakoff sets up for
58000 linguistic enquirey -- that is to say, only an "artificial
58100 intelligence" system.
58200
58300 Diskfile: Lakoff.Yaw[aim,doc]
58400
58500
58600 AIM-171, Roger Schank, ADVERBS AND BELIEF, June 1972, 30 pages.
58700
58800 The treatment of a certain class of adverbs in conceptual
58900 representation is given. Certain adverbs are shown to be
59000 representative of complex belief structures. These adverbs serve as
59100 pointers that explain where the sentence that they modify belongs in
59200 a belief structure.
59300
59400 AIM-172, Sylvia Weber Russell, SEMANTIC CATEGORIES OF NOMINALS FOR
59500 CONCEPTUAL DEPENDENCY ANALYSIS OF NATURAL LANGUAGE, July 1972,
59600 64 pages.
59700
59800 A system for the semantic categorization of conceptual objects
59900 (nominals) is provided. The system is intended to aid computer
60000 understanding of natural language. Specific implementations for
60100 "noun-pairs" and prepositional phrases are offered.
60200
60300 AIM-173, Gerald Jacob Agin, REPRESENTATION AND DESCRIPTION OF CURVED
60400 OBJECTS, October 1972,
60500
60600 This document describes some first efforts toward the goal of
60700 description and recognition of the general class of curved, three
60800 dimensional objects.
60900
61000 Three dimensional images, similar to depth maps, are obtained with a
61100 triangulation system using a television camera, and a deflectable
61200 laser beam diverged into a plane by a cylindrical lens.
61300
61400 Complex objects are represented as structures joining parts called
61500 generalized cylinders. These primitives are formalized in a volume
61600 representation by an arbitrary cross section varying along a space
61700 curve axis. Several types of joint structures are discussed.
61800
61900 Experimental results are shown for the description (building of
62000 internal computer models) of a handful of complex objects, beginning
62100 with laser range data from actual objects. our programs have
62200 generated complete descriptions of rings, cones, and snake-like
62300 objects, all of which may be described by a single primitive. Complex
62400 objects, such as dolls, have been segmented into parts, most of which
62500 are well described by programs which implement generalized cylinder
62600 descriptions.
62700
62800
62900 AIM-174, Morris, Francis Lockwood, CORRECTNESS OF TRANSLATIONS OF
63000 PROGRAMMING LANGUAGES -- AN ALGEBRAIC APPROACH, August 1972,
63100 124 p.
63200
63300 Programming languages and their sets of meanings can be modelled by
63400 general operator algebras; semantic functions and compiling functions
63500 by homomorphisms of operator algebras. A restricted class of
63600 individual programs, machines, and computations can be modelled in a
63700 uniform manner by binary relational algebras. A restricted class of
63800 individual manner by binary relational algebras. These two
63900 applications of algebra to computing are compatible: the semantic
64000 function provided by interpreting ("running") one binary relational
64100 algebra on another is a homomorphism on an operator algebra whose
64200 elements are binary relational algebras.
64300
64400 Using these mathematical tools, proofs can be provided systematically
64500 of the correctness of compilers for fragmentary programming languages
64600 each embodying a single language "feature". Exemplary proofs are
64700 given for statement sequences, arithmetic expressions, Boolean
64800 expressions, assignment statements, and while statement. Moreover,
64900 proofs of this sort can be combined to provide (synthetic) proofs for
65000 in principle, many different complete programming languages. One
65100 example of such a synthesis is given.
65200
65300
65400 AIM-175, Tanaka, Hozumi, HADAMARD TRANSFORM FOR SPEECH WAVE ANALYSIS,
65500 August 1972, 34 pages.
65600
65700 Two methods of speech wave analysis using the Hadamard transform are
65800 discussed. The first method is a direct application of the Hadamard
65900 transform for speech waves. The reason this method yields poor
66000 results is discussed. The second method is the application of the
66100 Hadamard transform to a log-magnitude frequency spectrum. After the
66200 application of the Fourier transform the Hadamard transform is
66300 applied to detect a pitch period or to get a smoothed spectrum. This
66400 method shows some positive aspects of the Hadamard transform for the
66500 analysis of a speech wave with regard to the reduction of processing
66600 time required for smoothing, but at the cost of precision. A formant
66700 tracking program for voiced speech is implemented by using this
66800 method and an edge following technique used in scene analysis.
66900
67000
67100 AIM-176, Feldman, J.A., Low, J.R., Swinehart, D.C., Taylor, R.H.,
67200 RECENT DEVELOPMENTS IN SAIL. AN ALGOL-BASED LANGUAGE FOR
67300 ARTIFICIAL INTELLIGENCE, (forthcoming).
67400
67500 AIM-177, Paul, Richard, MODELLING, TRAJECTORY CALCULATION AND SERVOING
67600 OF A COMPUTER CONTROLLED ARM, (forthcoming)
67700
67800
67900 AIM-178, Gill, Aharon, VISUAL FEEDBACK AND RELATED PROBLEMS IN COMPUTER
68000 CONTROLLED HAND EYE COORDINATION, October 1972, 134 pages.
68100
68200
68300 A set of programs for precise manipulation of simple planar bounded
68400 objects, by means of visual feedback, was developed for use in the
68500 Stanford hand-eye system. The system includes a six degrees of
68600 freedom computer controlled manipulator (arm and hand) and a fully
68700 instrumented computer television camera.
68800
68900 The image of the hand and manipulated objects is acquired by the
69000 computer through the camera. The stored image is analyzed using a
69100 corner and line finding program developed for this purpose. The
69200 analysis is simplified by using all the information available about
69300 the objects and the hand, and previously measured coordination
69400 errors. Simple touch and force sensing by the arm help the
69500 determination of three dimensional positions from one view.
69600
69700 The utility of the information used to simplify the scene analysis
69800 depends on the accuracy of the geometrical models of the camera and
69900 arm. A set of calibration updating techniques and programs was
70000 developed to maintain the accuracy of the camera model relative to
70100 the arm model.
70200
70300 The precision obtained is better than .1 inch. It is limited by the
70400 resolution of the imaging system and of the arm position measuring
70500 system.
70600
70700
70800
70900 AIM-179, Baumgart, Bruce G., WINGED EDGE POLYHEDRON REPRESENTATION,
71000 October 1972, 46 pages.
71100
71200 (forthcoming)
71300
71400
71500 AIM-180, Bajcsy, Ruzena, COMPUTER IDENTIFICATION OF TEXTURED VISUAL
71600 SCENES, October 1972, 156 pages.
71700
71800 This work deals with computer analysis of textured outdoor scenes
71900 involving grass, trees, water and clouds. Descriptions of texture are
72000 formalized from natural language descriptions; local descriptors are
72100 obtained from the directional and non-directional components of the
72200 Fourier transform power spectrum. Analytic expressions are obtained
72300 for orientation, contrast, size, spacing, and in periodic cases, the
72400 locations of texture elements. These local descriptors are defined
72500 over windows of various sizes; the choice of sizes is made by a
72600 simple higher- level program.
72700
72800 The process of region growing is represented by a sheaf-theoretical
72900 model which formalizes the operation of pasting local structure (over
73000 a window) into global structure (over a region). Programs were
73100 implemented which form regions of similar color and similar texture
73200 with respect to the local descriptors.
73300
73400 An interpretation is made of texture gradient as distance gradient
73500 in space. A simple world model is described. An interpretation of
73600 texture regions and texture gradient is made with a simulated
73700 correspondence with the world model. We find that a problem-solving
73800 approach, involving hypothesis-verification, more satisfactory than
73900 an earlier pattern recognition effort (Bajcsy 1970) and more crucial
74000 to work with complex scenes than in scenes of polyhedra. Geometric
74100 clues from relative sizes, texture gradients, and interposition are
74200 important in interpretation.
00100 XI. COGNIZANT PERSONNEL
00200
00300
00400 For contractual matters:
00500
00600 Office of the Research Administrator
00700 Stanford University
00800 Stanford, California 94305
00900
01000 Telephone: (415) 321-2300, ext. 2883
01100
01200 For technical and scientific matters:
01300
01400 Prof. Jerome Feldman
01500 Computer Science Department
01600 Stanford University
01700 Stanford, California 94305
01800
01900 Telephone: (415) 321-2300, ext. 4971
02000
02100 For administrative matters, including questions
02200 relating to the budget or property acquisition:
02300
02400 Mr. Lester D. Earnest, Executive Officer
02500 Mr. Norman R. Briggs, Business Manager
02600 Artificial Intelligence Laboratory
02700 Stanford University
02800 Stanford, California 94305
02900
03000 Telephone: (415) 321-2300, ext. 4971
03100